为什么不适用二叉平衡树(AVL树,红黑树)
1.二叉平衡树每个节点有两个子节点,这意味着树的高度更高,IO次数更多
2.查询效率不稳定,如果要查询的数据在叶子节点,需要进行多次IO
3.磁盘IO是以页为单位的,一页=4k,如果使用二叉平衡树,每个节点只存储两个子节点的引用(两路),也就是一次IO操作只加载了两个自己子节点的引用,太浪费了
因此要使用多路平衡树
为什么不使用B树
B+树与B树的区别:InnoDB中索引的实现采用的是B+树。B+树是B树的变种。B+树非叶子节点不存储数据只存储索引,在相同数据量下,B+树高度更低,且B+树叶子节点之间组成一个链表,便于遍历查询
B树:
我有一壶酒
足以慰风尘
尽倾江海里
赠饮天下人