B-树的理论分析

B-树

理论部分来自《数据结构 （C语言版）》 严蔚敏

背景知识

B-树是一种平衡的多路查找树，B-树其实就是B树，因为英文是B-Tree，翻译成了B-树。

B-树的数据结构常用于数据库索引技术和文件索引。由于数据库的索引是存储在磁盘上的，当数据量的比较大的时候，无法将整个索引一次全部加载到内存中，只能逐一加载磁盘页，使用B-树可以减少磁盘的I/O，提高查询效率，树的阶数取决于磁盘页的大小。非关系数据库MongoDB使用的B-树。

B-树的定义与特点

一颗 m {m} m阶的B-树需要满足特性

1. 树中每个结点至多有 m {m} m​​棵子树

2. 若根结点不是叶子结点，则至少有两棵子树

3. 除根之外的所有非叶子结点至少有 ⌈ m 2 ⌉ {\lceil \frac{m}{2} \rceil} ⌈2m​⌉棵子树（ m 2 { \frac{m}{2} } 2m​的值向上取整，不比 m 2 { \frac{m}{2} } 2m​小的最小整数）

4. 所有的非叶子结点中包含了以下信息数据

   （ n , A 0 , K 1 , A 1 , K 2 , A 2 , . . . , K n , A n {n,A_0,K_1,A_1,K_2,A_2,...,K_n,A_n} n,A0​,K1​,A1​,K2​,A2​,...,Kn​,An​​）

   其中 K i ( i = 1 , . . . , n ) {K_i}(i=1,...,n) Ki​(i=1,...,n)​​​​​为关键字，且 K i < K i + 1 ( i = 1 , . . . , n − 1 ) {K_i