算法——（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

相关文章