B Tree - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

【动画版】数据结构-B树【宁哥算法课堂】 B树自在人心，看不懂，我当场把这个树吃掉！ B树和B+树 B-树插入删除关键字数据结构

图解

详解

B树和B+树的插入、删除图文详解 推导B树的最大高度和最小高度得出B树的高度范围 经典数据结构 [ B树，B+树 ]+B树的应用 面试官问你B树和B+树，就把这篇文章丢给他 B树详细图解与Java完整实现

规则

• M阶代表一个树结点最多有多少个查找路径，M=M路，当M=2则是2叉树，M=3则是3叉

1. 排序方式：所有结点关键字是按递增次序排列，并遵循左小右大原则
2. 关键字数：非根结点的关键字数量>=ceil(m/2)-1个且<=M-1个（注：ceil()向上取整，如ceil(1.1)结果为2；例M = 5，2 <= key <= 4）
3. 子节点数：每个结点的子结点数 = 这个结点的关键字数 + 1
4. 叶子深度：所有叶子结点均在同一层、叶子结点除了包含了关键字和关键字记录的指针外也有指向其子结点的指针，只不过其指针地址都为null

要点

• B树是已排序的
• B树是平衡的，且树的高度大约在O(logn)
  • 决定搜索，插入，删除操作的时间复杂度
• B树是(a,b)-trees的一种，为(B,2B)-trees，2B代表阶数，例如(2,4)-trees为4阶B树
• 每层的结点个数 = 上层的结点数 + 上层的关键字数
• 每个结点的子结点数 = 这个结点的关键字数 + 1
• 递推最后的结果就是叶子层的结点数 = 所有的关键字数 + 根节点个数，就是N + 1

适用场景

• 操作系统的文件索引和数据库索引