大数据&云计算MySQL性能优化做得好的人，都懂的索引绝技( 三 ) |索引|性能优化|

AVL 树顺序插入 1~16 个节点，查找 id=16 需要比较的节点数为 4 。从查找效率而言， AVL 树查找的速度要高于红黑树的查找效率（AVL 树是 4 次比较，红黑树是 6 次比较）。从树的形态看来， AVL 树不存在红黑树的“右倾”问题。也就是说，大量的顺序插入不会导致查询性能的降低，这从根本上解决了红黑树的问题。

本文插图
总结一下 AVL 树的优点：

不错的查找性能（O（logn）），不存在极端的低效查找的情况。
可以实现范围查找、数据排序。

看起来 AVL 树作为数据查找的数据结构确实很不错，但是 AVL 树并不适合做 MySQL数据库的索引数据结构，因为考虑一下这个问题：
数据库查询数据的瓶颈在于磁盘 IO ，如果使用的是 AVL 树，我们每一个树节点只存储了一个数据，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比如查询 id=7 这个数据我们就要进行磁盘 IO 三次，这是多么消耗时间的。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。
磁盘 IO 有个有个特点，就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的，我们就可以根据这个思路，我们可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树， B+树的的设计原理了。
4、B树
下面这个 B 树，每个节点限制最多存储两个 key ，一个节点如果超过两个 key 就会自动分裂。比如下面这个存储了 7 个数据 B 树，只需要查询两个节点就可以知道 id=7 这数据的具体位置，也就是两次磁盘 IO 就可以查询到指定数据，优于 AVL 树。

本文插图
下面是一个存储了 16 个数据的 B 树，同样每个节点最多存储 2 个 key ，查询 id=16 这个数据需要查询比较 4 个节点，也就是经过 4 次磁盘 IO 。看起来查询性能与 AVL 树一样。

本文插图
但是考虑到磁盘 IO 读一个数据和读 100 个数据消耗的时间基本一致，那我们的优化思路就可以改为：尽可能在一次磁盘 IO 中多读一点数据到内存。这个直接反映到树的结构就是，每个节点能存储的 key 可以适当增加。
当我们把单个节点限制的 key 个数设置为 6 之后，一个存储了 7 个数据的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次。