文章未完成
B 树 （Balance-Tree）
多路查找树（multi-way search tree），其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。
B-树（即B树）是一种平衡的多路查找（又称排序）树，在文件系统中有所应用。主要用作文件的索引。其中的B就表示平衡(Balance) ，结点最大的孩子数目称为B树的 阶（Order）。
- 如果根结点不是叶结点，则其至少有两棵子树。
- 每一个非根的分支结点都有k-1个元素和k个孩子，其中[m/2]≤ k ≤ m。每一个叶子结点 n 都有k-1个元素，其中[m/2]≤ k ≤ m。
- 所有叶子结点都位于同一层次。
- 所有分支结点包含下列信息数据( n, A0, K1, A1, K2, A2, …, Kn, An )，其中: Ki( i=1, 2, …, n ) 为关键字，且Ki<Ki+1( i=1, 2, …, n-1 ); Ai ( i=0, 2, …, n) 为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki( i=1, 2, …, n ) ，An 所指子树中所有结点的关键字均大于Kn，n ( [m/2]-1 ≤ n ≤ m-1 ) 为关键字的个数(或 n+1 为子树的个数)。
B + 树
- B+ 树的叶子节点链表结构相比于 B- 树便于扫库，和范围检索。
- B+ 树支持range-query（区间查询）非常方便，而B树不支持。这是数据库选用B+树的最主要原因
- B 树 是B+树的变体，B树分配新结点的概率比B+树要低，空间使用率更高；