算法——(5)B/B+/红黑树

时间:2021-07-09 16:40:00

1. B树——lgdN

B树是平衡多路查找树,主要用于文件系统的索引。

1)定义:

对于一个度数为d的B树,

  • 每个结点最多有d个孩子
  • 如果根结点不是叶子结点,那它至少有两个孩子
  • 每个非叶子结点(非根结点)孩子:⎡d/2⎤<=n<=d
  • 每个非叶子结点含有n个关键字信息和n+1个指向孩子的指针,[n, p0, k1, p1, k2,p2,...,kn,pn]:
    1. ki(i=1,...n)为关键字,且按升序排列,即:k(i-1)<k(i)
    2. pi(i=0,...,n)为指向子树根的指针,且p(i-1)指向子树中所有的关键字均小于k(i),都大于k(i-1)
  • 每个叶子结点都在同一层,并且不包含任何关键字信息

 2)B树结点的代码实现

算法——(5)B/B+/红黑树
#define MAX 10  /*定义B树的最大阶数为10*/
typdef int KeyType /*KeyType为关键字类型*/
typedef struct BTNode{
int keynum; /*当前结点拥有的关键字数目*/
KeyType key[keynum+1]; /*key[0]不用,有keynum个关键字*/ struct BTNode *parent;
struct BTNode *child[keynum+1]; /*孩子结点的指针:child[0, 1, ...., keynum]*/ }
算法——(5)B/B+/红黑树

3)B树的复杂度和高度

对于一个含有n个关键字,d阶B树,它的高度h<=log⎡d/2⎤((n+1)/2)+1

  1. 根为1个结点,他至少有两个孩子,也就是第二层至少有2个结点,
  2. 其余非叶子结点,至少有:⎡d/2⎤个结点,因此第三层至少有:2*⎡d/2⎤
  3. 以此类推:第四层至少有:2*⎡d/2⎤2 、第五层至少有:2*⎡d/2⎤3,...,第l层至少有:2*⎡d/2⎤l-2个结点

所以:

算法——(5)B/B+/红黑树
1+2+2*⎡d/2⎤+...+2*⎡d/2⎤h-2 <=n

=>1+2*(1-2*⎡d/2⎤h-1)/(1-⎡d/2⎤)<=n

=>1+2*(⎡d/2⎤-1)(2*⎡d/2⎤h-1-1)/(⎡d/2⎤-1)<=n  因为d>2

=>h<=log⎡d/2⎤((n+1)/2)+1
算法——(5)B/B+/红黑树

4)检索一个key,其查找结点个数的复杂度:O(logd(N))

2. B+树——lndN

算法——(5)B/B+/红黑树

其中,浅蓝色的是磁盘块,其中存放了数据项和指针;例如:磁盘1包含了数据项:17,35,但是只是作为索引,而不是真的关键字,所有的关键字都包含在叶子结点。

例如:要查找29,那么首先会把磁盘块1由磁盘加载到内存,此时发生一次IO,在内存中用二分查找确定29在17和35之间,锁定磁盘块1的P2指针,内存时间因为非常短(相比磁盘的IO)可以忽略不计,通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存,发生第二次IO,29在26和30之间,锁定磁盘块3的P2指针,通过指针加载磁盘块8到内存,发生第三次IO,同时内存中做二分查找找到29,结束查询,总计三次IO。

B+树特性:

1. 内结点存放索引,关键字都存放在叶子结点。——每个磁盘盘存放数据量更多——减少IO次数

因为IO次数取决于B+树的高度h,假设当前数据表的数据为N,每个磁盘块的数据项的数量是m,则h=logm+1N。

2. 最左匹配原则。

当b+树的数据项是复合的数据结构,比如(name,age,sex)的时候,b+数是按照从左到右的顺序来建立搜索树的,比如当(张三,20,F)这样的数据来检索的时候,b+树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据;但当(20,F)这样的没有name的数据来的时候,b+树就不知道下一步该查哪个节点,因为建立搜索树的时候name就是第一个比较因子,必须要先根据name来搜索才能知道下一步去哪里查询。比如当(张三,F)这样的数据来检索时,b+树可以用name来指定搜索方向,但下一个字段age的缺失,所以只能把名字等于张三的数据都找到,然后再匹配性别是F的数据了, 这个是非常重要的性质,即索引的最左匹配特性。

3. 红黑树——lgN

红黑树是一种二叉搜索树。能保证在最坏的情况下,基本的几何操作均为O(lgN)

每个节点都含有:color、key、left、right,如果相应的指针域没有,则为NIL

满足五个性质

  1. 每个结点要不是红的就是黑的
  2. 根结点是黑的
  3. 每个叶结点(空结点NIL)是黑的
  4. 如果一个结点是红的,则它两个孩子都是黑的
  5. 对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点

http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html