数据结构之B树_四阶树

在学习B树之前，我们需要先了解一下2-3-4树。

2-3-4树的定义

2-节点

包含一个键(及其对应的值)和两条链，左连接指向2-3-4树中都小于该节点，右链接所指向的值都大于该节点。

3-节点

包含两个键(及其对应的值)和三条链，左链接指向2-3-4树 中的键都小于该节点，中链接指向的2-3-4树中的键都位于该节点的两个键之间，右连接指向的2-3-4树 中的键都大于该节点。

4-节点

包含三个键(及其对应的值)和四条链，左链接指向2-3-4树 中的键都小于该节点，左中链接和右中指向的2-3-4树中的键都位于该节点的两个键之间，右连接指向的2-3-4树 中的键都大于该节点。

2-3-4树的特点：所有叶子节点拥有相同的深度。

 

B树

特点

B树中允许一个节点包含多个Key，可以是3个、4个、5个甚至是更多，并不确定，需要看具体实现。现在我们选择一个参数M来构建一个B树，我们可以将其称为M阶的B树。那么这棵树会有以下特点：

• 每个节点最多有M-1个Key,并且以升序排列
• 每个节点最多能有M个子节点
• 根节点至少有两个子节点

 

存储数据

若参数M选择为5，那么每个节点最多包含4个键值对，我们以5阶B树为例，看看B树的数据存储。

（1）在空树中插入39

（2）继续插入22,97,和41

（3) 继续插入53（53的会插入在41和97的中间，那么这个节点将不满足每个节点最多有M-1个Key，所以只能让41(中间键)升序）

 （4) 继续插入13和21

（5)继续插入40（40的会插入在39的后边，那么这个节点将不满足每个节点最多有M-1个Key，所以只能让22(中间键)升序）

（6)继续插入30,27,33,36,35,34,24,29 （7)继续插入26 （27需要向上浮）

……

按照这样的方式依次往下进行， B树就被构建了出来。

优势

在实际应用中B树的阶数一般比较大(通常大于100)，所以，即使存储大量的数据，B树的高度仍然比较小，这样在某些引用场景下，就能体现出它的优势：降低对于树的访问次数，实现树的平衡。