文章目录

  • 简介
  • 如何评价索引的数据结构设计好坏
  • 二叉树的局限性
  • 什么是B树
  • 什么是B+树
  • 总结
  • 参考文献

简介

我们在上一节中说过，索引其实是一种数据结构，那它到底是一种什么样的数据结构呢？本节将简单介绍一下几个问题：

  • 什么样的数据结构更适合作为索引？平衡二叉树是否合适？
  • 什么是B树和B+树，为什么我们常用B+树作为索引的数据结构？

如何评价索引的数据结构设计好坏

由于索引是存放在磁盘上的，所以我们在通过索引来查找某行数据的时候，大量的时间其实是花在了磁盘的IO上。

因此，如果我们能让索引的数据结构尽量减少与磁盘的IO次数，那么就能减少查询所消耗的时间，这样的数据结构就是更好的。

二叉树的局限性

二叉树是一种高效且常见的数据检索方式。其时间复杂度为O(log2N)，那么，采用二叉树作为索引的数据结构合适么？

让我们看一下最基础的二叉搜索树，假设需要搜索的数值是key：

  • 如果key大于根节点，则在右子树中进行查找；
  • 如果key小于根节点，则在左子树中进行查找；
  • 如果key等于根节点，那么就是找到了这个节点。

举个例子，（34，22，89，5，23，77，91）创造出来的二叉搜索树为：

最多只需要经过3次搜索，就能找到指定值。

但是存在特殊的情况，比如说以(5, 22, 23, 34, 77, 89, 91)的顺序创造出来的二分查找树为：

在这个树里，最多需要经过7次比较之后才能找到指定的节点。

因为第二棵树实际上已经退化成了一张链表，查找数据的时间复杂度变成了O(n)。

当然，如果使用平衡二叉搜索树的话，就可以解决这个问题，因为平衡二叉数在二分搜索树的基础上添加了约束，其约定每个节点的左子树和右子树的高度差不能超过1，即左右子树依然是平衡二叉树。

常见的平衡二叉树有很多种，比如说平衡二叉搜索树、红黑树、数堆、伸展树。平衡二叉搜索树是最早提出的一种平衡二叉树。因此我们一般说的平衡二叉树，其实就是平衡二叉搜索树，搜索时间复杂度就是 O ( l o g2n )O(log_2n)O(log2​n)。

由于每访问一次节点就要进行一次磁盘IO操作，所以对平衡二叉搜索树来讲，一般会进行 O ( l o g2n + 1 )O(log_2n+1)O(log2​n+1)次IO操作。比如说一个5层的平衡二叉树，共31个节点，正常会进行5次IO操作。树的深度越大，意味着IO操作的次数就越多，就越影响整体数据查询的效率。

所以我们可以考虑下，如果将二叉树换成M叉树（M>2），是不是就可以降低树的高度了呢？比如说，同样的31个节点，使用三叉树来存储的话，树深就变成了 l o g3( 31 + 1 )log_3(31+1)log3​(31+1)，就是4层。

可以看到，此时树的高度降低了，当数据量足够大的时候，确实比二叉树要好一些。

什么是B树

上一小节中，我们讲到了M叉树（M>2）的表现要优于二叉树。因此一个节点应该允许有M个子节点。

B树就是这么被提出来的。B树，即Balance Tree，就是平衡的多路搜索树，它的高度远小于平衡二叉搜索树的高度。在文件系统和数据库系统中的索引结构经常使用B树来实现。

B树的结构如下图：

可以看到，B树中每个节点最多可以包含M个子节点，而M则称为是B树的阶。

同时，每个磁盘块中包括了关键字（如17/35）和子节点的指针（如P1、P2和P3）。指针数是关键字数量 + 1。

对一个100阶的B树来讲，如果有3层的话最多可以存储 （ 99 ∗ 1 + 99 ∗ 10 01+ 99 ∗ 10 02） = 999999（99*1 + 99*100^1 + 99*100^2）=999999（99∗1+99∗1001+99∗1002）=999999，约100w的索引数据。

在存储数据相同的情况下，其高度远远低于二叉树的高度。

简单总结下，一个M阶B树（M>2）的特性：

  • 根节点的孩子节点数为[2, M]
  • 每个中间节点包含n-1个关键字和n个孩子，其中n的取值范围是[ceil(M/2)，M]
  • 假设中间节点的关键字为 k 1, k 2,…., k n−1 k_1, k_2,….,k_{n-1} k1​,k2​,….,kn−1​，且关键字按照升序排序，即 k i< k i+1 k_i < k_{i+1} ki​<ki+1​。此时n-1个关键字相当于是划分出了n个数值范围，因此对应着n个指针，即 P 1, P 2,…., P nP_1, P_2,….,P_n P1​,P2​,….,Pn​，其中， P 1P_1 P1​指向关键字小于 K 1K_1 K1​的子节点， P 2P_2 P2​指向关键字属于( k 1, k 2)(k_1, k_2) (k1​,k2​)的节点，以此类推。
  • 所有叶子节点位于同一层。

可以结合上面图来查看刚刚总结的这些特性。

相比平衡二叉树，B树的深度要更低，从而要进行的磁盘IO操作也更少，在数据查询中的效率就显得更高。

虽然M越大，一次读进内存的用来比较的数据就越多，但这个比较的过程是在内存里进行的，时间消耗可以忽略不计。

什么是B+树

B+树是对B树的改进，主流的DBMS都支持B+树的索引方式，比如说MySQL。

B+树和B树的差异在哪儿呢？

  • 每个节点内的关键字数量和孩子数量一样。而B树中，孩子数量 = 关键字数量 + 1；
  • 非叶子节点的关键字也会同时出现在子节点里，并且是子节点关键字里的最大或者最小。而B树中，则不会同时出现在子节点中；
  • 非叶子节点仅用于索引，不保存数据记录，所有的数据记录都是放在叶子节点里。而B树中，所有的节点都是可以既保存索引，也保存数据记录。
  • 所有关键字都在叶子节点里出现，每个节点内部所有关键字按照大小从小到大顺序排列，所有叶子节点构成一个有序链表。

比如说下面这张图，就是一棵B+树：

比如说，想查找关键字16，就会自顶向下逐层进行查找，先后访问磁盘块1、磁盘块2、磁盘块7。三次IO操作即可。

在IO的次数上，B+ 树看起来似乎跟B树差不多，那么B+树到底好在哪儿呢？

这个要看B+树和B树的根本差异：B+树的中间节点并不直接存储数据。

这样有什么好处呢？

首先，B+树查询效率更加稳定。B+树每次只有访问到叶子节点后才能取出数据，而B树中，由于非叶子节点也可以存储数据，这就造成了查询效率不稳定的情况，有时候需要访问到叶子节点才能找到数据，有时候走一半到非叶子节点就可以找到数据。时间不好量化。

其次，B+树查询效率更高。通常B+树比B树更矮胖（非叶子节点只存放索引，因此一个节点可以放更多关键字，从而减少深度），所需的磁盘IO就更少。同样的磁盘页大小，B+树可以存储更多的节点关键字。

在做区间查询的时候，B+树的效率同样比B树高。因为B+树里，所有的关键字都出现在叶子节点上，并通过有序链表进行了链接，非常适合寻找范围数据。而B树则需要通过中序遍历扫一遍才能完成范围数据的查找，效率要低很多。

总结

索引在使用时，时间的消耗主要是两部分带来的，一是读取磁盘块来取出里面保存的索引值数据，二是比较索引值数据。不过比较的工作是在内存中进行的，速度很快，所以这部分时间其实可以忽略不计。

因此，制约索引使用速度的唯一因素，就是与磁盘块的IO。只要能减少这块的IO，就能减少索引在使用时的时间消耗，从而提升整个查询的效率。

构造索引的时候，我们更倾向于采用矮胖的数据结构，因此平衡二叉树的结构被果断舍弃了。

B树和B+树都可以作为索引的数据结构，在MySQL中采用的是B+树，其查询性能更加稳定，在磁盘页大小相同的情况下，树的构造更加矮胖，所需要的IO次数更少，也更适合进行关键字的范围查找。

参考文献

  1. 24丨索引的原理：我们为什么用B+树来做索引？