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

梦里梦外; 2023-09-26 16:02 81阅读 0赞

## 前言 ##

索引其实就是一种数据结构，我们进来就来看一下索引的数据结构究竟是怎样的？对索引底层的数据结构有了更深入的了解后，就会有利于我们了解索引的使用原则。感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

## 二叉树结构 ##

在正式开讲前我们先来看一下最基础的二叉树，顾名思义，每个节点最多有两个子节点，分别是左子节点和右子节点。通过图像看更直接点。

![format_png][]

二叉树的特点：

1.  每个节点最多有两棵子树，即不存在超过度为2的节点，第 i 层最多有 2i-1 个结点。
2.  如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
3.  二叉树的子树有左右之分，且左右不能颠倒。

拿上图举例，树的深度是3，当我们查找数字8的节点，需要3次比较就可以找到节点，但是存在特殊的情况，当我们的数据量特别大的时候，这时候二叉树的深度可能非常大，这样磁盘I/O操作次数会增多，我们知道数据查询的时间主要依赖磁盘I/O的次数，会影响整体数据查询的效率。

针对这个问题，如何能降低这个受树的深度呢？接下来我们看下B树。

## BTree结构 ##

B树是一种平衡的多分树，又叫多路平衡查找树，通常我们说m阶的B树，我们来看下他的数据结构：

![format_png 1][]

BTree有如下特性：

*  树中每个节点最多包含m个子节点
 *  除根节点与叶子节点外，每个节点至少有\[ceil(m/2)\]个子节点。
 *  若根节点不是叶子节点，则至少有两个子节点。
 *  所有的叶子节点都在同一层。
 *  每个叶子节点由n个key与n+1个指针组成，其中\[ceil(m/2)-1\] < n < m-1.

以上图为例，我们来模拟下查找key为15的data的过程：

1.  根据根结点指针读取文件目录的根磁盘块1。【磁盘IO操作1次】
2.  我们与根节点的关键字(17,35)进行比较，15小于17那么得到指针p1。
3.  根据指针p1找到磁盘块2并读取数据。【磁盘IO操作2次】
4.  我们与根节点的关键字(8,12)进行比较，15大于12，因此我们得到指针p3。
5.  根据指针p3找到磁盘块7并读取数据。【磁盘IO操作3次】
6.  我们与根节点的关键字(13,15)进行比较，我们找到15，获取15所对应的数据data。

由此可见，当存储的数据量大时，BTree的深度明显减少，可以减少磁盘I/O的次数，从而提高查询的效率。

在BTree中，非叶子节点也会存储数据，这样会造成存储空间的浪费和查询效率不稳定的情况，如有时候访问到了非叶子节点就可以找到关键字，而有时候需要访问到叶子节点才能找到关键字，有没有改进的方法呢？

## B+Tree结构 ##

基于上述问题B+树做出了改进，与Btree不同之处在于:

*  每个节点的指针上限为2d而不是2d+1；
 *  内节点不存储data，只存储key；
 *  叶子节点不存储指针；
 *  为所有叶子节点增加一个链指针（注意链上的数据是有序的）,树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录

![format_png 2][]

比如当我们查找key=16的查找过程如下：

1.  根据根结点指针读取文件目录的根磁盘块1。【磁盘IO操作1次】
2.  与根节点的关键字(1,18,35)进行比较，16在1和18之间，得到指针P1。
3.  根据指针p1找到磁盘块2并读取数据。【磁盘IO操作2次】
4.  我们与根节点的关键字(1,18,14)进行比较，16大于14，因此我们得到指针p3。
5.  根据指针p3找到磁盘块7并读取数据。【磁盘IO操作3次】
6.  我们与根节点的关键字(14,16，17)进行比较，我们找到16，获取16所对应的数据data。

## 总结 ##

本文总结了常见的树结构，我们主要关注BTree和B+Tree就可以了，其中B+Tree是BTree个改进版，二者的区别如下：

在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息， 数据记录都存放在叶子节点中， 这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

在B+Tree上通常有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。所以我们除了可以对B+Tree进行主键的范围查找和分页查找，还可以从根节点开始，进行随机查找。

[format_png]: https://img-blog.csdnimg.cn/img_convert/e2e8ea120a7a4b619d91b06dd1f12651.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/b6f22623d062fa79979bc06c05bb848d.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/eb2272b7a1cf7bb06d18e98857c61fbc.webp?x-oss-process=image/format,png