image
image
image
image
————————————
image
image
image
image
image
image
image
image
image
————————————
image
image
image
image
image
image
image
image
image
image
image
image
image
image
二叉查找树的结构：
image
第1次磁盘IO：
image
第2次磁盘IO：
image
第3次磁盘IO：
image
第4次磁盘IO：
image
image
image
image
image
下面来具体介绍一下B-树（Balance Tree），一个m阶的B树具有如下几个特征：
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
image
image
image
image
image
image
image
第1次磁盘IO：
image
在内存中定位（和9比较）：
image
第2次磁盘IO：
image
在内存中定位（和2，6比较）：
image
第3次磁盘IO：
image
在内存中定位（和3，5比较）：
image
image
image
image
image
image
自顶向下查找4的节点位置，发现4应当插入到节点元素3，5之间。
image
节点3，5已经是两元素节点，无法再增加。父亲节点 2， 6 也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。于是拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。
image
image
image
image
自顶向下查找元素11的节点位置。
image
删除11后，节点12只有一个孩子，不符合B树规范。因此找出12,13,15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子。（这个过程称为左旋）
image
image
image
image
image
●本文编号420，以后想阅读这篇文章直接输入420即可。
●输入m获取文章目录
