MYSQL的B+Tree索引树⾼度如何计算
我们使⽤MySQL数据库的时候，绝⼤部分的情况下在使⽤InnoDB存储引擎，偶尔会使⽤MyISAM存储引擎，⾄于其他存储引擎，我相信⼤家都很少接触到，甚⾄可能都没有听说过。所以本⽂只讲解InnoDB和MyISAM两个存储引擎的索引，以及如何计算这两个存储引擎的索引结构B+Tree的⾼度。
InnoDB
InnoDB主键索引⽰意图如下，⾮叶⼦节点上没有实际的数据，只有叶⼦节点上才有实际的数据，并且叶⼦节点之间有指针串联指向下⼀个叶⼦节点，这样能够提升范围查询的效率：
InnoDB B+Tree主键索引⽰意图
InnoDB使⽤了聚簇索引（Clustered），即所有⼆级索引聚集在主键索引上，对InnoDB存储引擎表的任何访问，最终⼀定要搜索主键索引树，⼆级索引的⽰意图如下：
InnoDB B+Tree⼆级索引⽰意图
在InnoDB中，⼆级索引（所有不是主键索引的索引）上没有实际的数据，取⽽代之的是主键索引的值。这样的话，如果是基于⼆级索引的查询，会先在⼆级索引上搜索得到主键索引的值，然后再去主键索引树上搜索，得到最终的⾏数据。
这就意味着，⾄少有⼀次索引查，可能会有两次索引查，其中⼀定有⼀次主键索引查。
所以，在InnoDB中，主键要设计的尽量⼩，主键越⼩，⼆级索引也会越⼩。满⾜需求的情况下，SMALLINT优先于INT，INT优先于BITINT，INTEGER类型优先于VARCHAR类型。如果主键⽤更⼤的数据类型，由于⼆级索引上有主键索引的值，那么不只是主键索引树变的更⼤更⾼，其他的⼆级索引树也会更⼤更⾼，这绝对是⼀个糟糕的做法。
MyISAM
MyISAM没有使⽤聚簇索引，所以主键就是⼀个普通的唯⼀索引，并且基于索引查询只会搜索当前索引，不会和其他索引有任何关系，任意两个索引之间互不影响。如下图所⽰，是MyISAM的主键索引⽰意图，我们可以看到，索引树的叶⼦节点上只有表中⾏数据的地址，⽽不是和InnoDB⼀样，有实际的数据：
MyISAM的主键索引⽰意图
如下图所⽰，是MyISAM的⼆级索引⽰意图，我们可以看到，其结构⼏乎和主键索引⽰意图⼀样，叶⼦结点上也有表中⾏数据的地址：
mysql下载32位MyISAM的⼆级索引⽰意图
B+TREE⾼度
了解B+Tree索引的⼤概结构后，我们接下来讲解⼀下如何计算索引树的⾼度。
我们先做如下假设：
表的记录数是N；
每个BTREE节点平均有B个索引KEY（即1,2,3,4,5… …）；
很明显，这时候B+TREE索引树的⾼度就是logBN（等价于logB/logN）。需要说明的是，这⾥的对数以及接下来有对数的地⽅应该是下图中的对数，笔者不知道如何将word中的对数复制过来，所以请将就⼀下下（尴尬￣□￣）：
对数
另外我们知道，由于索引树每个节点⼤⼩固定，所以索引KEY越⼩，B值就越⼤，即每个BTREE节点上可以保存更多的索引KEY。并且索引树的⾼度是logBN，那么B值越⼤，索引树的⾼度越⼩，那么基于索引查询的性能就越⾼。所以我们可以得到结论：相同表记录数的情况下，索引KEY越⼩，索引树⾼度就越⼩。
现在，我们假设表有1600w条记录（因为2^24≈1600w，便于接下来的计算），如果每个节点保存64个索引KEY，那么索引⾼度就是(log10^7)/log64 ≈ 24/6 = 4。
所以，由上⾯的演算可知，我们要计算⼀张表的索引树的⾼度，还只需要知道⼀个节点有多⼤，从⽽就能知道每个节点能存储多少个索引KEY。现代数据库经过不断的探索和优化，并结合磁盘的预读特点，每个索引节点⼀般都是操作系统页的整数倍，操作系统页可通过命令得到该值得⼤⼩，且⼀般是4094，即4k。⽽InnoDB的pageSize可以通过命令得到，默认值是16k。
关于预读：在索引树上查到某个KEY（例如id=3），需要先到这个KEY所在的叶⼦节点（因为B+Tree索引只有叶⼦节点上有具体的数据），这个查过程从根节点到叶⼦节点，需要经过整个树。当到叶⼦节点后，会根据预读原理将整个节点数据全部加载到内存中，然后基于⼆分法到最终的KEY。
OK，到这⾥，我们距离真正计算⼀个拥有1600w数据的表的索引树的⾼度，只差每个索引KEY所占空间了。
以BIGINT为例，存储⼤⼩为8个字节。INT存储⼤⼩为4个字节（32位）。索引树上每个节点除了存储KEY，还需要存储指针。所以每个节点保存的KEY的数量为pagesize/(keysize+pointsize)（如果是B-TREE索引结构，则是pagesize/(keysize+datasize+pointsize)）。
假设平均指针⼤⼩是4个字节，那么索引树的每个节点可以存储16k/((8+4)*8)≈171。那么：⼀个拥有1600w数据，且主键是BIGINT类型的表的主键索引树的⾼度就是(log10^7)/log171 ≈ 24/7.4 ≈ 3.2。
假设平均指针⼤⼩是6个字节，那么索引树的每个节点可以存储16k/((8+6)*8)≈146。那么：⼀个拥有1600w数据，且主键是BIGINT类型的表的主键索引树的⾼度就是(log10^7)/log146 ≈ 24/7.2 ≈ 3.3。
假设平均指针⼤⼩是8个字节，那么索引树的每个节点可以存储16k/((8+8)*8)≈128。那么：⼀个拥有1600w数据，且主键是BIGINT类型的表的主键索引树的⾼度就是(log10^7)/log128 ≈ 24/7 ≈ 3.4。
由上⾯的计算可知：⼀个千万量级，且存储引擎是MyISAM或者InnoDB的表，其索引树的⾼度在3~5之间。
说明：这⼀段对索引树⾼度的计算，都是基于B+Tree，即InnoDB和MyISAM存储引擎的索引⽤到的数据结构。⽽B-TREE索引节点上不仅保存了索引和指针，还保存了具体的⾏数据，索引树的⾼度算法略有不同。
总结
索引树的⾼度是⼀个⾮常重要的东西，因为当查的条件能⽤到索引时，就不⽤全表扫描，⽽是只需要在索引上搜索，从索引的根节点到叶⼦节点。并且很明显的是：索引树越⾼，性能就会越差。我们假设在最糟糕的情况下，索引⼀点没有被加载到内存中，⽽是全部持久化在磁盘上。那么索引树有多⾼，就表⽰查询⾄少需要多少次IO操作。即使实际情况中，由于表的数据更多，索引也会很⼤，不⼤
可能全部被保存在缓存中。⽽且如果是⼆级索引搜索，IO次数还要翻倍（⼆级索引搜索+主键索引搜索），这对性能是⼀个很⼤的影响。
这也是MySQL数据库使⽤B+Tree作为索引结构的原因：尽可能降低索引树的⾼度。⽽红⿊树等其他数据结构，树的⾼度要深的多的多。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。