大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构,为什么B-Tree和B+Tree在被如此广泛用于索引?先从数据结构的角度来分析。

几种常见的树结构

二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree),红黑树(Red-Black Tree ),B-tree/B+-tree/ B*-tree (B~Tree)。前三都是二叉查找树, 查找时间复杂度O(log2N)与树的深度有关,降低深度自然也能提高查询效率。

面临的问题

实际的大规模存储中,在实现索引查询的背景下,树能存储的数据量是有限的,大数据量情况下导致树过深造成磁盘I/O读写过于频繁(磁盘构造有关),导致查询效率底下。那么减小树的深 度就成为有效的提高查询效率的手段。那么很自然一个想法就是多叉树结构

磁盘的构造

磁盘上数据通过一个三维地址唯一标示:柱面号、盘面号、块号(磁道上的盘块)。

磁盘的读写需要经过三个步骤:

  • 定位(查找):移动臂根据柱面号使磁头移动到所需要的柱面
  • 确定盘面:这时根据盘面号来确定指定盘面上的磁道
  • 确定块号:将指定块号的磁道段移动至磁头下

访问具体信息由三步时间组成:

  • 查找时间(seek time) Ts:完成上面步骤一所需时间,代价最高,最大到0.1s左右。
  • 等待时间(latency time) Tl:上述三步耗时。
  • 传输时间(transmission time) Tt: 数据通过系统总线传送到内存的时间。

B-Tree、B+Tree为什么适合做索引

  • B-Tree、B+Tree是多路搜索树,查询任意一个节点,IO次数是恒定的,最多需要访问h个节点(h为树高)。
  • mysql巧妙地将一个节点的大小设置了一页的大小,每次磁盘读取一页的数据就能在一次IO 的情况下将整个节点的数据读出来。
  • mysql B-Tree一般高度不超过3,100阶的高度为3的B-Tree,可以存100100100=10^6的数据,基本上3次IO就可以完成索引。

为什么不用红黑树

因为红黑树是二叉树,存储大量数据的时候树的高度会非常大,会造成多次IO读取,性能很差。如上所述10^6的数据在红黑树中就不可能在3次IO内完成,因此红黑树不适合作为外存索引。

总结

由此可以看出提高索引查询效率的关键在于减少磁盘的定位和IO次数,而减少磁盘IO关键在于降低树的高度。