SQL进阶理论篇（四）：索引的结构原理（B树与B+树）

简介

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

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

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

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

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

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

在这里插入图片描述

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

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

在这里插入图片描述

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

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

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

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

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

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

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

上一小节中，我们讲到了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*100^1 + 99*100^2）=999999$ ，约100w的索引数据。

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

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

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