扫码关注公众号
B树&B+树两者有何异同呢?
结点结构不同B树的所有节点既存放键(key)也存放数据(data),而B+树只有叶子节点存放key和data,其他内节点只存放key。叶子结点之间的关系不同B树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。增加一个链指针检索过程不同B树的检索的过程相当于对范围内的每个节点的关键字做二分查找,可能还没有到达叶子节点,检索就结束了。(中途结束)而B+树的检索效率就很稳定了,任何查找都是从根节点到叶子节点的过程,叶子节点的顺序检索很明显。(必然会到达叶子节点)
B树优秀在哪里?
B树相对于B+树的优点是,如果经常访问的数据离根节点很近,而B树的非叶子节点存储关键字数据的地址,所以这种数据检索的时候会要比B+树快。
为什么B+树比较优秀?
1、B+树查找速度更稳定因为B+树的所有数据都存放在叶子结点上2、B+树的层级更少相较于B树B+每个非叶子节点存储的关键字数更多,树越矮查询数据越快;3、B+树全表扫描更快因为它支持区间访问,因为它的叶子节点是相连的,是个单链表,而B树需要一层一层的访问4、B+树天然具备排序功能因为叶子节点数据构成了一个有序链表
B树和二叉查找树的性能对比?
B树包括B+树的设计思想都是尽可能的降低树的高度,以此降低磁盘IO的次数,因为一个索引节点就表示一个磁盘页,页的换入换出次数越多,表示磁盘IO次数越多,越低效。B树算法减少定位数据所在的节点时所经历的磁盘IO次数,从而加快存取速度。假设一个节点可以容纳100个值,那么3层的B树可以容纳100万个数据。(根节点100值,第二层可以存储99个节点(k-1),也就是99*100个值,第三层可以存储,(99*100-1)*100)结果是近似100万个数据。而如果使用二叉查找树,则需要将近20层,也就是进行20次磁盘IO,性能差距如此之大。如mongoDB数据库使用,单次查询平均快于Mysql(但侧面来看Mysql至少平均查询耗时差不多)。