B+树

磁盘是以磁头和旋转分块来存蓄内存的数据结构或者数据,

假设我们有一个员工表,放入磁盘,磁盘一个块能存蓄4个员工信息,那么,100个员工就是25块磁盘

 

 那现在需要查找50号员工张三, 那是非常废时间的,为此我们建立了索引,并且将索引页放入磁盘的块中

 

这也就是树的前身,但是树的设定我们知道是左右子节点和一些基本的叶子组成,

而key即数值,way即路线,永远满足的way=key-1

(在这里我们需要引进b-tree的知识)

而这个M阶即m课子树即指针也就是线

 这是B树

 

 

 

就如这样一个M-way插入10.20.30,首先插入10然后20比0大 按照2叉树的概念,应该插在右孩子,看图可知这是非常费时间的数据结构,类似于线性结构。

 

当然看了上面的m-way之后发现简直就是浪费时间的结构

显然这不适合我们的b-tree,所以B-tree就在树,二叉树,的基础上加了一些规则

第一就是每个节点必须至少填充一半。

第二就是节点最少有两个chirld

第三就是保持统一高度

第四创建过程自下而上

那我们来见一个例子吧

 一个m=4 way的的m-way,即(m-1)key所以当用b-tree的规则就是满三个块满了,50没地方所以去了新建的第二块,

这时40就提出去向上生长,因为至少填充一半就是最少2个,50又新建了满足规则的只有40

同理新加60 70 80中的70也是第三个提上去,向上生长。

 

 

 同样加入30 35

<h2> 就是不停的拆分,然后向上生长</h2>

 这就是最终的b+tree

 

原文地址:https://www.cnblogs.com/yangj-Blog/p/12944301.html