mysql红黑树_为什么Mysql用B+树做索引而不用B-树或红黑树？

5

平衡二叉树不足

考虑到极端情况下，每次插入的数据都比上一次插入的数据大，那么用平衡二叉树就会以线性方式进行存储，时间复杂度为O(n)。数据量很大时，在mysql中一张表存储百万条数据是很正常的一件事，这样会导致树的深度更深，mysql读取时消耗大量io。

mysql进行过磁盘读取时，是以页为单位进行读取，每个节点表示一页。而平衡二叉树每个节点存储一个关键词，导致存储空间被浪费。

6

B-树相比平衡二叉树优点

每个节点存储多个多个关键词，合理利用空间大小，每次mysql进行读取时，都会进行预读取，每次把该节点数据读取出来并存储到内存中

B-树中每个节点存储的关键词变多，导致存储相同数量的数据，B-树的深度相比平衡二叉树深度更浅，减少了数据的查找次数和复杂度

7

B+树对比红黑树

红黑树多用于内部排序，即全放在内存中

B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构

红黑树和平衡二叉树有相同缺点，每个节点存储一个关键词，数据量大时，导致红黑树的深度很深，mysql每次读取时消耗大量io

8

B+树相比B-树的优点

B+树非叶子节点只存储key值，而B-树存储key值和data值，这样B+树每次读取时可以读取到更多的key值

mysql进行区间访问时，由于B+树叶子节点之间用指针相连，只需要遍历所有的叶子节点即可；而B-树则需要中序遍历那样遍历

B+树非叶子