b树与b+树总结

前言

最近工作中涉及到了挺多的索引的问题，仔细梳理下来发现自己掌握的并不深入，所以记录一下。

这篇文章与索引有关, 主要介绍索引常用的两种树结构, b树与b+树, 以及两者的区别。

B树

b树和b-树是一个意思(以后别被面试官忽悠了)。它是一个特殊的二叉树，可以包含多于2个的子节点。它的作用和其他类型的数据库索引一样，都是为了加快数据的查询速度。采用了这种树结构的索引，可以在构建索引的时候，将数据分成多个块，每个块称为一个节点。节点之间的数据是有序的，这样可以加快数据的查找速度。(把这个理解成链表就行了)

以下通过一个图示来举例子：

1
2
3
4
5

        10
      /    \
   5,6      13,15
  /   \    /  |  \
 3     7  12  14  20

假设我要查找一个值为14的数据。

1. 首先从根节点开始查找，发现目标数比根节点所存的数字要大，继续查找右边的节点(类似二分查找法)
2. 到13,15这个节点, 发现目标数比13要大, 且比15要小, 所以定位到这个节点的中间子节点
3. 到第三层的节点, 发现此节点保存的数据恰好为14, 所以查找成功, 返回指向行数据的指针
4. 通过返回的指针找到对应的数据

不难发现，b树正是通过每次查找都能减少近一半的数据量，从而提高查找效率(对数级的时间复杂度)。

b树的这个"b"代表着balance(平衡)，每次新增、更新、删除数据时，b树都会自动调整，保持树的平衡。

B+树

b+树是b树的变种，也相当于加强版的b树。

它相比于b树，多了以下特点：

• B树的节点(根节点/父节点/中间节点/叶子节点)中没有重复元素，B+树有
• 非叶子节点不存储数据，只存储指向子节点的指针
• 叶子节点之间存在指针连接

这里我去网上截个图来举例：

假设要查找15这个数据，b+树的查找过程如下：

1. 从根节点开始查找，发现目标数比根节点所存的数字要大，继续查找右边的节点
2. 到15,18这个节点, 发现目标数匹配了，但是因为b+树的非叶子节点不存储数据，所以继续往下查找
3. 最终找到目标数的叶子节点，返回指向行数据的指针
4. 通过返回的指针找到对应的数据

两者对比

b+树做为b树的变种，它肯定存在某些优势的：

1. b+树的查询效率更加稳定，因为非叶子节点不存储数据，所以每次查找都是一样的时间复杂度。而b树因为中间节点也存储数据，所以可能查询一下就返回了，也可能要查找很多次。
2. 还是由于b+树的非叶子节点不存储数据，所以b+树的数据存储更加紧凑，可以存储更多的数据。可以这么理解：非叶子节点不存储数据，所以同样大小的磁盘页可以加载更多的节点，从而减少IO次数。
3. b+树的叶子节点之间存在指针连接，所以可以很方便的进行范围查询。意味着，如果要查找一个范围的数据，只需要找到范围的起始节点，然后通过指针连接，一直查找到范围的结束节点即可。而b树需要做中序遍历