search

zhanggao / learnNotes

2 stars 2 forks source link

B树(B-树)、B+树、B*树的区别 #17

Open zhanggao opened 4 years ago

zhanggao commented 4 years ago

平衡二叉树： 任一节点的高度差的绝对值不超过1， 左边小于中间，右边大于中间，没有相等的值。

zhanggao commented 4 years ago

B树（B-树）： 所有节点关键字依次递增，左边小于右边 非叶子节点的子节点大于1小于等于M(M>2) 枝节点关键字数量大于ceil(M/2-1)，小于等于M-1。（ ceil(1.01)=2 ） 所有叶子节点都在同一层

zhanggao commented 4 years ago

B+树： B+树的非叶子节点只做数据的索引，不保存关键字，B树所有节点都保存数据 B+树叶子节点保存了所有数据的指针，所有查询必须到叶子节点才能查到数据 B+树叶子节点从小到大排序，左边的结尾保存了右边开头的指针

B+树查找稳定 B+树所有叶子构成了有序链表，所以可以范围查找，全节点遍历更快 如果经常访问的节点离根节点很近，这种情况B树查找更快

zhanggao commented 4 years ago

B树： B+树初始化关键字个数是ceil(m/2),B树的初始化关键字个数是ceil(2/3m) B树索引节点左边的结尾也会保存右边开头的指针，所以B*树枝节点满了采用分裂的方式

由于B*树可以向兄弟节点转移关键字的特性，所以分解次数变少