数据结构与算法(十三)B+树

性质

M 阶的B+树

  • 每个结点最多存储m-1个元素

  • 每个结点最多有m个子结点

  • 根结点要么为空,要么为独根,否则至少有2个子结点

  • 除根节点外,每个结点至少有m/2个子结点,除不尽则往上取整,7/2=3.5 --> 4

  • 叶子结点的高度一致

  • 只有叶子结点才存储数据

  • 叶子结点之间通过指针相连,提高区间的访问性能

图示

B树.png

构建过程

  • 自下往上构建
  • 先分裂(m/2)再插入

构建过程.png

#   B+树 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×