B树和B+树

一、B树其实就是是B-树,是一种多路平衡查找树,它的每个节点最多包含k个孩子,k被称为B树的阶,k的大小取决于磁盘页的大小,B树主要应用于文件系统和部分数据库索引,如MongoDB,一个m阶的B树具有以下几个特点:

1.根结点至少有两个子女。

2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。


B树特点


二、B+树

B+树特点:

节点的子树数和关键字数相同(B 树是关键字数比子树数少一)节点的关键字表示的是子树中的最大数,在子树中同样含有这个数据叶子节点包含了全部数据,同时符合左小右大的顺序