————————————
————————————
二叉查找树的结构:
第 1 次磁盘 IO:
第 2 次磁盘 IO:
第 3 次磁盘 IO:
第 4 次磁盘 IO:
下面来具体介绍一下 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 个孩子包含的元素的值域分划。
第 1 次磁盘 IO:
在内存中定位(和 9 比较):
第 2 次磁盘 IO:
在内存中定位(和 2,6 比较):
第 3 次磁盘 IO:
在内存中定位(和 3,5 比较):
自顶向下查找 4 的节点位置,发现 4 应当插入到节点元素 3,5 之间。
节点 3,5 已经是两元素节点,无法再增加。父亲节点 2, 6 也是两元素节点,也无法再增加。根节点 9 是单元素节点,可以升级为两元素节点。于是 拆分 节点 3,5 与节点 2,6,让根节点 9 升级为两元素节点 4,9。节点 6 独立为根节点的第二个孩子。
自顶向下查找元素 11 的节点位置。
删除 11 后,节点 12 只有一个孩子,不符合 B 树规范。因此找出 12,13,15 三个节点的中位数 13,取代节点 12,而节点 12 自身下移成为第一个孩子。(这个过程称为 左旋)
漫画算法系列 »