B树

B树

B树是一种平衡的多路搜索树, 多用于文件系统、数据库的实现

B树的性质(m阶)

  • 假设一个节点存储的元素为x

    • 根节点: 1 <= x <= m -1
    • 非根节点 (m/2)(向上去整) <= x <= m - 1

  • 子节点个数: y = x + 1

添加

  • 新添加的元素必定是添加到叶子节点
    • 上溢: 添加后节点的元素个数超过限制
    • 上溢解决: 找到中间的元素往上合并, 左右元素分裂成两个节点

删除

  • 真正被删除的元素在叶子节点中
    • 下溢: 删除后节点的元素个数少于限制
    • 下溢解决: 兄弟节点能借元素就借, 不能借就将父节点中间元素挪下来跟左右子节点和并

了解b树是为了学习红黑树, 因为红黑树与4阶b树相匹配

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • B树（转）
    原文链接 B树 1.前言： 动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（...
    非典型程序员阅读 1,214评论 0赞 3
  • B树
    B树 1.前言： 动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balan...
    铁甲依然在_978f阅读 1,473评论 0赞 4
  • 12-B树
    B树(B-tree，B-树) B树是一种平衡的多路搜索树，多用于文件系统，数据库的实现 仔细观察B树，有什么眼前一...
    ducktobey阅读 341评论 0赞 0
  • 数据结构 - B树(多路查找树)
    二叉搜索树(Binary Search Tree).AVL树(艾薇儿树). 之前我们了解的树，都是一个节点可有多个...
    翀鹰精灵阅读 659评论 0赞 1
  • 剪发
    剪短千丝发， 理顺烦恼缘， 喜迎新气象， 让爱从头来！ �������林灵 三千青丝为谁留， 愿结发同修共进。 守...
    好帅麻阅读 155评论 0赞 1