不谈需求谈实现，都是耍流氓。

那么MySQL的需求是什么？

核心需求：精准查询，范围查询，排序

那么，哈希好像不大行，范围查询很慢。链表也不得行，要遍历。剩下的就是树了。广为人知的，二叉搜索树，AVL树，红黑树，B树等等。

二叉搜索树

二分查找，小的放左边，大的放右边。

局限性：

• 根节点的选取很重要，极限情况就成了一个链表了。（都比根节点大，就都在右边了）
• 树的层数不固定，这都还好。
• 数的层次过大，毕竟子的数量都是2，数据量大了可能几万层了，这样不管是内存（放不下）还是磁盘IO都很难（每一字访问节点都是一次读取）。

AVL树

在二叉树的基础上做了平衡处理，虽然极大避免了退化问题，层数也固定了，但是最大的问题---层数过多的问题没有解决。

红黑树

红黑树只是优化了插入、更新，弱化了平衡，在更新和搜索中取了折中。但是一样，层数过多的问题没有解决。

B-树（B树，不是B减树）

为了降低层数，最简单的，一层多放一点元素不就好了。

根据 Knuth 的定义，一个 m 阶的B树是一个有以下属性的树：

• 每一个节点最多有 m 个子节点
• 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
• 如果根节点不是叶子节点，那么它至少有两个子节点
• 有 k 个子节点的非叶子节点拥有 k − 1 个键
• 所有的叶子节点都在同一层

（晕了就过吧，理解就行）

总之就是让一个节点有多个关键字，再口语一点就是可以存多个数字。

这样，访问一个节点的时候， 就可以多拿出来一点了，也就是“页”。

缺点还是有的，访问下一页要怎么办？回到父节点到兄弟节点。于是，B+树来了。

B+树

很明显，将叶子节点用链表串联起来了， 还有就是子节点中包含了父节点的信息，比如22，这样的好处就是，可以直接访问到下一个，即，遍历了叶子节点就是遍历了全表。

并不完美

B树还有一个问题就是页分裂。

当我们要插入550的时候，pageA满了，则分裂成两页，但是分裂后的A还有一个位置，就是“空洞”。

当然这个问题在如今这个磁盘不值钱的年代已经不是什么大问题了，实在不行还有重建表这种功能。

结语

• 如果有不对的地方欢迎指正。
• 如果有不理解的地方欢迎指出我来加栗子。
• 如果感觉OK可以点赞让更多人看到它。