4 MySQL学习---MySQL索引( 二 ) _生活百科

此时的二叉查找树如下图所示：

文章插图
因此，需要平衡二叉树来降低最坏情况下二叉查找树的深度。
平衡二叉树（AVL树）的引入平衡二叉查找树除了具备二叉查找树的特点，最主要的特征是树的左右两个子树的层级最多相差1 。其在插入删除数据时通过左旋或右旋操作来保持树的平衡，不会出现左右子树一边很高、一边很矮的情况。
平衡二叉树如下图所示：

文章插图
平衡二叉树通过对二叉查找树进行平衡化，从而保证了对树进行操作的时间复杂度不会退化。因此，它的平均时间复杂度为O(log2N) 。
毫无疑问，平衡二叉树的查找效率是非常高的。但是当数据量非常大，树存储的元素数量是有限的的，这样会导致平衡二叉树的平均深度过大而造成磁盘IO读写过于频繁，进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有节点的情况。

时间复杂度和树高相关。树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。磁盘每次寻道时间为10ms，在表数据量大时，查询性能就会很差。（1百万的数据量，log2n约等于20次磁盘IO，时间20*10=0.2s）
平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高。

B树是解决这个问题的很好的数据结构。
前置知识：磁盘IO与预读上文提到了磁盘访问，这里简单介绍一下磁盘IO和预读，磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分：
寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；旋转延迟就是我们经常说的磁盘转速磁盘转速，比如一个磁盘7200转/min，表示每分钟能转7200次，也就是说一秒能转120次，旋转延迟就是1/120/2=4.17ms，也就是半圈的时间（这里有两个时间：平均寻道时间，受限于目前的物理水平，大概是5ms的时间，找到磁道了，还需要找到你数据存在的那个点，寻点时间，这寻点时间的一个平均值就是半圈的时间，这个半圈时间叫做平均延迟时间，那么平均延迟时间加上平均寻道时间就是你找到一个数据所消耗的平均时间，大概9ms，其实机械硬盘慢主要是慢在这两个时间上了，当找到数据然后把数据拷贝到内存的时间是非常短暂的，和光速差不多了）；传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。
那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17=9ms左右，听起来还挺不错的，但要知道一台500-MIPS（Million Instructions Per Second）的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的消耗的时间段下cpu可以执行约450万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难，所以我们要想办法降低IO次数。下图是计算机硬件延迟的对比图，供大家参考：

文章插图
考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页（page）。具体一页有多大数据跟操作系统有关，一般为4KB或8KB，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。