1. 索引数据结构
1.1 二分查找
我们可以考虑用有序数组作为索引的数据结构。
- 有序数组：二分查询效率非常高，但是更新数据的时候会出现一个问题， 可能要挪动大量的数据（改变 index），所以只适合存储静态的数据。
- 链表：支持频繁的修改，比如插入数据，但链表的查找效率低。
所以，有没有可以使用二分查找的链表呢？ 为了解决这个问题，BST（Binary Search Tree）也就是我们所说的二叉查找树诞生 了。
1.2 二叉查找树
二叉查找树[1]的时间复杂和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。所以，平衡二叉树有诞生了，叫做 Balanced binary search trees，或者 AVL 树（AVL 是 发明这个数据结构的人的名字）。
1.3 平衡二叉树
平衡二叉树[2]的左右子树深度差绝对值不能超过 1。因此，树的最大高度为 O(logn)。但问题是，树的高度还是太高，导致可能需要多次 IO 才能读取到数据。
举个例子：假设有 1000w 条记录，则树的高度为 log(1000w) = 23 层，也就是说 1000w 条记录最多需要 23 次 IO，效率太低。
1.4 B 树
多路平衡查找树[3]也叫做 B Tree（B 代表平衡），可以在一个节点存储多条记录。跟 AVL 树一样，B 树在枝节点和叶子节点存储键值、数据地址、节点引用。 它有一个特点：分叉数（路数）永远比关键字数多 1。
同样，1000w 条记录，假设一条记录是 1K。MySQL 页大小默认为 16 KB，则一页可以存储 16 条记录（对应 17 个分叉），也就是说一次 IO 可以读取 16 条记录。这 1000w 条记录树的高度为为 log17(1000w) = 6 层，也就是说 1000w 条记录最多需要 6 次 IO，相比平衡二叉树已经提升了很多。
1.5 B+ 树
B+ 树[4] 在 B 树的基础上更进一步，非叶子节点只保存索引信息，叶子节点才保存数据。这样每页可以保存更多的索引，树的高度也更低。
还是上面的例子：假设一条记录是 1K，一个叶子节点（一页）可以存储 16 条记录。非叶 子节点可以存储多少个指针？ 假设索引字段是 bigint 类型，长度为 8 字节。指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节。非叶子节点（一页）可以存储 16384 / 14 = 1170 个这样的 单元（键值+指针），代表有 1170 个指针。 那么：
若有收获，就点个赞吧
0 人点赞
