节点|曾经，我以为我很懂MySQL索引...( 二 ) |磁盘|字段|from|

其实最终选用 B+树是经历了漫长的演化：

二叉排序树 → 二叉平衡树 → B-Tree（B树） → B+Tree（B+树）

有小伙伴问我“B 树跟 B-树有什么区别”?这里普及一下， MySQL 数据结构只有B-Tree(B 树)和 B+Tree(B+树) ，多只是读法不同罢了， “B-Tree” 一般统称为 B 树，你叫他 B-树也行!
还有小伙伴提到的红黑树，是编程语言中的存储结构，不是 MySQL 的;如 Java 的 HashMap 就是用的链表加红黑树。
好了，今天就带着大家一起看一下演化成 B+树的过程吧。
【节点|曾经，我以为我很懂MySQL索引...】B+Tree 索引的前世今生
①二叉排序树
理解 B+树之前，简单说一下二叉排序树，对于一个节点，它的左子树的孩子节点值都要小于它本身，它的右子树的孩子节点值都要大于它本身。
如果所有节点都满足这个条件，那么它就是二叉排序树。 (此处可以串一下二分查找的知识点)

本文插图

上图是一颗二叉排序树，你可以尝试利用它的特点，体验查找 9 的过程：

9 比 10 小，去它的左子树(节点 3)查找。
9 比 3 大，去节点 3 的右子树(节点 4)查找。
9 比 4 大，去节点 4 的右子树(节点 9)查找。
节点 9 与 9 相等，查找成功。

一共比较了 4 次，那你有没有想过上述结构的优化方式?
②AVL 树(自平衡二叉查找树)

本文插图

上图是 AVL 树，节点个数和值均和二叉排序树一摸一样。
再来看一下查找 9 的过程：

9 比 4 大，去它的右子树查找。
9 比 10 小，去它的左子树查找。
节点 9 与 9 相等，查找成功。

一共比较了 3 次，同样的数据量比二叉排序树少了一次，为什么呢?因为 AVL 树高度要比二叉排序树小，高度越高意味着比较的次数越多;不要小看优化的这一次，假如是 200w 条数据，比较次数会明显地不同。
你可以想象一下一棵 100 万节点的平衡二叉树，树高 20 。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。
也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的!
③B 树(Balanced Tree)多路平衡查找树，多叉的
B 树是一种多路自平衡搜索树，它类似普通的二叉树，但是 B 树允许每个节点有更多的子节点。
B 树示意图如下：