我们一起聊聊MySQL 索引的底层逻辑 _MySQL

数据结构以及算法【我们一起聊聊MySQL 索引的底层逻辑】索引的本质其实就是一种数据结构。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找，这种复杂度为 O(n) 的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找、二叉树查找等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

文章插图
图片
1.1 B-Tree为了描述 B-Tree ，首先定义一条数据记录为一个二元组 [key, data] ， key 为记录的键值，对于不同数据记录， key 是互不相同的；data 为数据记录除 key 外的数据。那么 B-Tree 是满足下列条件的数据结构：

d 为大于 1 的一个正整数，称为 B-Tree 的度。
h 为一个正整数，称为 B-Tree 的高度。
每个非叶子节点由 n-1 个 key 和 n 个指针组成，其中 d<=n<=2d。
每个叶子节点最少包含一个 key 和两个指针，最多包含 2d-1 个 key 和 2d 个指针，叶节点的指针均为 null。
所有叶节点具有相同的深度，等于树高 h。
key 和指针互相间隔，节点两端是指针。
一个节点中的 key 从左到右非递减排列。
所有节点组成树结构。
每个指针要么为 null，要么指向另外一个节点。
如果某个指针在节点 node 最左边且不为 null，则其指向节点的所有 key 小于 v(key_1)，其中 v(key_1) 为 node 的第一个 key 的值。
如果某个指针在节点 node 最右边且不为 null，则其指向节点的所有 key 大于 v(key_m)，其中 v(key_m) 为 node 的最后一个 key 的值。
如果某个指针在节点 node 的左右相邻 key 分别是 key_i 和 key{i+1} 且不为 null ，则其指向节点的所有 key 小于 v(key{i+1}) 且大于 v(key_i)。

如下是一个 d = 2 的 B-Tree 示意图。

文章插图
图片
由于 B-Tree 的特性，在 B-Tree 中按 key 检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的 data ，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到 null 指针，前者查找成功，后者查找失败。B-Tree 上查找算法的伪代码如下：

BTree_Search(node, key) {if(node == null) return null;foreach(node.key){if(node.key[i] == key) return node.data[i];if(node.key[i] > key) return BTree_Search(point[i]->node);}return BTree_Search(point[i+1]->node);}data = https://www.isolves.com/it/sjk/MYSQL/2024-01-03/BTree_Search(root, my_key);

关于 B-Tree 有一系列有趣的性质，例如一个度为 d 的 B-Tree，设其索引 N 个 key ，则其树高 h 的上限为 log_d((N+1)/2) ，检索一个 key ，其查找节点个数的渐进复杂度为 O(log_dN)。从这点可以看出，B-Tree 是一个非常有效率的索引数据结构。
1.2 B+TreeB-Tree 有许多变种，其中最常见的是 B+Tree ，例如 MySQL 就普遍使用 B+Tree 实现其索引结构。与 B-Tree 相比，B+Tree 有以下不同点：

每个节点的指针上限为 2d 而不是 2d+1。
内节点不存储 data ，只存储 key ；叶子节点不存储指针。

如下是一个简单的 B+Tree 示意。

文章插图
图片
由于并不是所有节点都具有相同的域，因此 B+Tree 中叶节点和内节点一般大小不同。这点与 B-Tree 不同，虽然 B-Tree 中不同节点存放的 key 和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中 B-Tree 往往对每个节点申请同等大小的空间。一般来说， B+Tree 比 B-Tree 更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关，将在下面讨论。