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

毫无疑问，平衡二叉树的查找效率是非常高的。但是当数据量非常大，树存储的元素数量是有限的的，这样会导致平衡二叉树的平均深度过大而造成磁盘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 ，这个理论对于索引的数据结构设计非常有帮助。
B树（平衡二叉树的改造）的引入对于平衡二叉树，考虑到磁盘IO对查询数据效率的影响，我们更希望出现“矮胖”而不是“瘦高”树，因为这样可以显著减少查询时的IO次数，增加查询效率。那么我们如何能够降低树的高度呢？
假如key为8字节（bigint类型），每个节点有两个指针，每个指针为4个字节（B），一个节点占用的空间16个字节（8+4*2=16）
因为在MySQL的InnoDB存储引擎一次IO会读取的一页（默认一页16KB）的数据量，而二叉树一次IO有效数据量只有16字节，空间利用率极低。为了最大化利用一次IO空间，一个简单的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储1000个索引（16kB/16B=1000），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建100万条数据，树的高度只需要2层就可以（1000*1000=106），也就是说只需要2次磁盘IO就可以查询到数据。磁盘IO次数变少了，查询数据的效率也就提高了。、
B树又叫多路平衡树，通常我们所说的m阶/m叉的B树，它必须满足以下条件：