henryspace

记录精彩的程序人生 开始使用

B 树是啥

二叉树有点像个拖着尾巴的链表,其中平衡二叉树的查找效率最好。

1,B树即Balance树,平衡树,由平衡二叉树发展而来,常见的有B-树, B+树,B*树等,都是平衡树。

2,B-树相对于平衡二叉树,在叶子结点的key不限于2个,而是key-1个,所以分块多了,查找的效率也大大提升。

3,B+树相对于B-树,效率又提升了,数据不存放在父节点而是叶子节点(而B-树的key,value都存在节点上没分开),看起来就是叶子节点的数据其实是下一层节点的key;另外就是B+每一层的数据建立了链地址,每一层相当于一个链表,这样查找每一层就不需要递归了,直接在链表里查,效率更快,这也是为啥数据库都选用这种来实现查找。

4,B树是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;B树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。

请成为永远疯狂永远浪漫永远清澈的存在。

评论
留下你的脚步