面试题------B树和B+树的区别
B树特点:
1.节点排序(节点存储:地址信息+索引+表结构中除了索引外的其他信息)
2.一个节点可以存多个元素,元素也排序
B+树的特点:
1.拥有B树的特点
2.叶子节点之间有指针
3.非叶子节点上的元素在叶子节点上都冗余了,也就是叶子节点中存储了所有的元素,并且排好顺序。
4.(非节点存储:地址信息+索引、叶子节点存储:索引+表结构中除了索引外的其他信息)
在Mysql中一个innodb页就是一个B+树节点,一个innodb页默认16kb,所以一般情况下,一颗两层的B+树,可以存2000万行左右的数据
区别:
B树key和value都在节点上。并且叶子节点之间没有关系。
而B+树的非叶子节点没有存value。叶子节点之间有双向指针,有引用链路。
查找方式不同,因为B树的key和value都存在节点上,因此在查找过程中,可能不用查找的叶子节点就找到了对应的值。
而B+树需要查找到叶子节点,才能获取值
结论:由于B树每个节点都存储了一条记录的所有数据,因此每次IO开销大。以及B+树的叶子节点有指针,可以很好的支持全表扫描、范围查找。