天天看点

Mysql索引为什么使用B+树

为什么不适用二叉平衡树(AVL树,红黑树)

Mysql索引为什么使用B+树

1.二叉平衡树每个节点有两个子节点,这意味着树的高度更高,IO次数更多

2.查询效率不稳定,如果要查询的数据在叶子节点,需要进行多次IO

3.磁盘IO是以页为单位的,一页=4k,如果使用二叉平衡树,每个节点只存储两个子节点的引用(两路),也就是一次IO操作只加载了两个自己子节点的引用,太浪费了

因此要使用多路平衡树

为什么不使用B树

B+树与B树的区别:InnoDB中索引的实现采用的是B+树。B+树是B树的变种。B+树非叶子节点不存储数据只存储索引,在相同数据量下,B+树高度更低,且B+树叶子节点之间组成一个链表,便于遍历查询

B树:

Mysql索引为什么使用B+树

我有一壶酒

足以慰风尘

尽倾江海里

赠饮天下人