树 - (二叉查找树,红黑树,B树)- B树
虽是读书笔记,但是如转载请注明出处 http://segmentfault.com/blog/exploring/
.. 拒绝伸手复制党
以下是算法导论第十八章的学习笔记
一个问题
如果红黑树中的每个黑结点吸收它的红子女,并把它们的子女并入自身,描述这个结果的数据结构。
(2-3-4树
)
or
假设将一棵红黑树的每一个红结点 “吸收” 到它的黑色父结点中,来让红结点的子女变成黑色父结点的子女(忽略关键字的变化)。当一个黑结点的所有红色子女都被吸收后,其可能的度是多少?此结果树的叶子深度怎样
B树 - 平衡多路查找树
这段整理自July's blog 和 自己的理解
磁盘读取数据(把数据从外存调入内存)是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间上。因此我们应该尽量将相关信息存放在同一盘块,同一磁道中,这样一次IO时间就可以。或者至少放在同一柱面或相邻柱面上,以求在读/写信息时尽量减少磁头来回移动的次数,避免过多的查找时间。
所以,在大规模数据存储方面,大量数据存储在外存磁盘中,而在外存磁盘中读取/写入块(block)中某数据时,首先需要定位到磁盘中的某块,如何有效地查找磁盘中的数据,需要一种合理高效的外存数据结构,B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。
与红黑树不同之处在于,B树的节点可以有许多个,从几个到几千个。不过 B 树与红黑树一样,一棵含 n 个结点的 B 树的高度也为 O(logn)
,但可能比一棵红黑树的高度小许多,因为对数的底由红黑树的2
变为t
(t为最小度数
). 因为它的分支因子比较大。所以,B 树可以在 O(logn)
时间内,实现各种如插入(insert),删除(delete)等动态集合操作。
B树的每个节点根据实际情况可以包括大量信息和子女(当然是不能超过磁盘块的大小,因为我们从磁盘上读取信息的时候一般都是按照磁盘块进行的,一个磁盘快对应一个节点,每次检索B树的时候遇到一个节点,也就对应一次磁盘的访问操作,如果一个节点大于了一个磁盘块,那么访问一个节点需要两次磁盘访问,效率就不行了,一般块的大小在 1k~4k 左右 )
如图 17是磁盘文件名;小红方块表示这个 17 文件内容在硬盘中的存储位置;p1 表示指向 17 左子树的指针
B树性质
如果是一棵 m 阶的 B 树,那么有:
-
m
阶树的孩子数
$$ ceil( \frac{m}{2} ) \leq 孩子数 \leq m $$ - 除根结点和叶子结点外,其它每个结点至少有
ceil(m / 2)
个孩子(其中 ceil(x) 是一个取上限的函数); - 除根结点之外的结点的关键字的个数 n 必须满足:
$$ ceil(\frac{m}{2})-1 \leq n \leq m-1 $$(叶子结点也必须满足此条关于关键字数的性质) - 树的高度
$$ h = \log_{t}{(\frac{n+1}{2} + 1)} $$
$$ t = ceil( \frac{m}{2} )$$
节点
B 树的类型和节点定义如下图所示:
查找操作
假如每个盘块可以正好存放一个 B 树的结点(正好存放 2 个文件名)。那么一个 BTNODE 结点就代表一个盘块,而子树指针就是存放另外一个盘块的地址。
下面,咱们来模拟下查找文件 29 的过程:(详细见July博客)
- 根据根结点指针找到文件目录的根磁盘块 1,将其中的信息导入内存。【磁盘 IO 操作 1 次】
- 此时内存中有两个文件名 17、35 和三个存储其他磁盘页面地址的数据。根据算法我们发现:17<29<35,因此我们找到指针 p2。
- 根据 p2 指针,我们定位到磁盘块 3,并将其中的信息导入内存。【磁盘 IO 操作 2 次】
- 此时内存中有两个文件名 26,30 和三个存储其他磁盘页面地址的数据。根据算法我们发现:26<29<30,因此我们找到指针 p2。
- 根据 p2 指针,我们定位到磁盘块 8,并将其中的信息导入内存。【磁盘 IO 操作 3 次】
- 此时内存中有两个文件名 28,29。根据算法我们查找到文件名 29,并定位了该文件内存的磁盘地址。
分析上面的过程,发现需要 3 次磁盘 IO 操作和 3 次内存查找 操作。关于内存中的文件名查找,由于是一个有序表结构,可以利用折半查找提高效率。至于 IO 操作是影响整个 B 树查找效率的决定因素。
查询需要O(h)
存取的磁盘页面数
插入操作
插入元素 - 检查是否存在
- 存在,不插入
- 不存在,在叶子节点插入新的元素
叶子节点空间足够(
#<m-1
),插入叶子节点空间不够(
#=m-1
),插入进去,然后分裂
,中间节点上移
如果导致父节点满了,父节点再分裂;若导致根节点满了。这样导致树的
高度
+1
删除操作
高度为h
的树,只需要O(h)
次磁盘存取操作。
删除元素 - 检查BTree是否存在该节点
- 不存在,不删除
- 存在,删除之,然后判断:该元素是否有左右孩子
若有,则
上移``孩子
中相近元素 (“左孩子最右边的节点” 或 “右孩子最左边的节点”) 到该节点 - to step *若无,直接删除 , - to step *
-
step *: 如果删除之后或者移动之后,导致某节点的元素数目小于
ceil(m/2)-1
;则需要查看某相邻的兄弟节点是否丰满
(大于ceil(m/2)-1
)step *1. 父节点
下降
一个关键字到该节点;下降
--判断兄弟 --
step *2.1 如果其某个相邻兄弟
结点中比较丰满(元素个数大于ceil(m/2)-1
),则可以借给父结点一个元素,即将最丰满的相邻兄弟结点中上移
到父节点中上调
step *2.2 如果其相邻兄弟
都刚脱贫,即借了之后其结点数目小于ceil(m/2)-1
,则该结点与其相邻的某一兄弟结点进行合并
成一个结点,以此来满足条件合并