B+树和红黑树

Question

老师您好，既然红黑树插入删除速度快，为什么数据库索引不用红黑树而用B+树呢？

Answer 1

翔仔 2020-10-25 23:02:07

同学好，就和课程讲解mysql的索引的时候我们提到的一样，b+树的存储数据更合理些，因为同一层能存储更多的数据，是扁平的形状，这样能够将更多层的数据载入到缓存里面，提升性能

• 提问者 Kevin7012055 #1

  老师那为什么红黑树不能设计成一层存储多个节点的数据结构呢？

• 翔仔 回复 提问者 Kevin7012055 #2

  这是由红黑树的特性决定的，因为同样的结点数的话，红黑树的高度最多为2log(n+1)，而B+树的高度最多为(logt (n+1)/2)+1,随着t增大高度会更小，IO次数也会减少