MySQL索引背后的数据结构及算法原理( 二 )


BTree_Search(node, key) {if(node == null) return null;foreach(node.key){if(node.key[i] == key) return node.data[i];if(node.key[i] > key) return BTree_Search(point[i]->node);}return BTree_Search(point[i+1]->node);}data = https://www.isolves.com/it/sjk/MYSQL/2020-08-18/BTree_Search(root, my_key);关于B-Tree有一系列有趣的性质,例如一个度为d的B-Tree,设其索引N个key,则其树高h的上限为(log_d((N+1)/2)),检索一个key,其查找节点个数的渐进复杂度为(O(log_dN)) 。从这点可以看出,B-Tree是一个非常有效率的索引数据结构 。
另外,由于插入删除新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质,本文不打算完整讨论B-Tree这些内容,因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法,有兴趣的朋友可以在本文末的参考文献一栏找到相应的资料进行阅读 。
B+TreeB-Tree有许多变种,其中最常见的是B+Tree,例如MySQL就普遍使用B+Tree实现其索引结构 。
与B-Tree相比,B+Tree有以下不同点:
每个节点的指针上限为2d而不是2d+1 。
内节点不存储data,只存储key;叶子节点不存储指针 。
图3是一个简单的B+Tree示意 。

MySQL索引背后的数据结构及算法原理

文章插图
 
图3
由于并不是所有节点都具有相同的域,因此B+Tree中叶节点和内节点一般大小不同 。这点与B-Tree不同,虽然B-Tree中不同节点存放的key和指针可能数量不一致,但是每个节点的域和上限是一致的,所以在实现中B-Tree往往对每个节点申请同等大小的空间 。
一般来说,B+Tree比B-Tree更适合实现外存储索引结构,具体原因与外存储器原理及计算机存取原理有关,将在下面讨论 。
带有顺序访问指针的B+Tree一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问指针 。
MySQL索引背后的数据结构及算法原理

文章插图
 
图4
如图4所示,在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree 。做这个优化的目的是为了提高区间访问的性能,例如图4中如果要查询key为从18到49的所有数据记录,当找到18后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率 。
这一节对B-Tree和B+Tree进行了一个简单的介绍,下一节结合存储器存取原理介绍为什么目前B+Tree是数据库系统实现索引的首选数据结构 。
为什么使用B-Tree(B+Tree)上文说过,红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础 。
一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上 。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度 。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数 。下面先介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率 。
主存存取原理目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却具体差别,抽象出一个十分简单的存取模型来说明RAM的工作原理 。
MySQL索引背后的数据结构及算法原理

文章插图
 
图5
从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据 。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元 。图5展示了一个4 x 4的主存模型 。
主存的存取过程如下:
当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取 。
写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作 。
这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的 。


推荐阅读