(数)B-树与B+树.ppt

第28讲10 3 3B 树 B 树的概念 B 树的查找 B 树的插入与生成 B 树中关键字的删除 B 树的存储结构 1 B 树的概念 m阶B 树 一棵m阶B 树或者是一棵空树 或者是满足下列特性的m叉树 1 树中每个结点至多有m棵子树 2 若根结点不是叶子结点 则至少有两棵子树 3 除根之外的所有非终端结点至少有 m 2 棵子树 4 每个结点中包含下列信息数据 n p0 k1 p1 k2 p2 kn pn 其中 n为结点中关键字的个数 除根结点外 其他所有结点的关键字个数n 满足 m 2 1 n m 1 ki 1 i n 为关键字且ki ki 1 1 i n 1 pi 0 i n 为指向子树根结点的指针 且满足pi 0 i n 1 所指子树中所有结点的关键字均大于ki且小于ki 1 pn所指子树中所有结点的关键字均大于kn 5 所有叶子结点都在同一层上 即B 树是所有结点的平衡因子均为0的多叉查找树 1 10 2 3 6 2 13 16 2 1 2 2 4 5 3 7 8 9 2 11 12 2 14 15 4 17 18 19 20 一棵5阶的B 树 B 树与B 树 2 B 树的存储结构 在B 树的存储结构中 各结点的类型定义如下 defineMAXM10 B 树的最大阶数typedefintKeyType KeyType为关键字类型typedefstructnode intkeynum 结点中的关键字个数structnode parent 双亲结点指针keytypekey MAXM 关键字数组key 1 keynum key 0 不用structnode ptr MAXM 孩子结点指针数组ptr 0 keynum BTNode B 树结点类型 B 树与B 树 3 B 树的查找 在B 树中查找关键字k的算法为 将k与根结点中的key i 1 i n 进行比较 1 若k key i 则查找成功 2 若kkey n 则沿着指针ptr n 所指的子树继续查找 B 树与B 树 在B 树上查找关键字k的程序为 typedefstruct BTNode pt 指向找到的结点inti 1 m 在结点中的关键字序号inttag 1 查找成功 O 查找失败 Result B 树查找结果类型intm m阶B 树 为全局变量intMax m阶B 树中每个结点的至多关键字个数 Max m 1intMin m阶B 树中非叶子结点的至少关键字个数 Min m 1 2intSearch BTNode p KeyTypek 在指针p所指结点中查找关键字k 在p key 1 keynum 中查找i 使得p key i key i 1 for inti 0 ikeynum B 树与B 树 ResultSearchBTree BTNode t KeyTypek 在m阶B 树t中查找关键字k 返回结果 pt i tag 若查找成功 则特征值tag 1 指针pt所指结点中第i个关键字等于k 否则特征值tag 0 等于k的关键字应插入在指针Pt所指结点中第i和第i 1个关键字之间 BTNode p t q NULL p指向待查结点 q指向p的双亲intfound 0 i 0 Resultr while p NULL 返回k的位置 或插入位置 B 树与B 树 1 10 2 3 6 2 13 16 2 1 2 2 4 5 3 7 8 9 2 11 12 2 14 15 4 17 18 19 20 在上述的5阶B 树中 查找关键字18 B 树与B 树 B 树高度定理 任意一棵含N 0 个关键的m 2 阶B 树的高度h满足 h log m 2 n 1 2 1证明 略 见书P 323由B 树高度定理可知 在B 树中查找结点的时间复杂度为 O log m 2 n 1 2 4 B 树中关键字的插入与生成 B 树的生成 从空树起逐个插入关键字便可生成B 树 将关键字k插入到B 树中的过程分两步完成 1 利用B 树的查找算法找出该关键字的插入结点 注意B 树的插入结点一定是叶子结点 2 若该结点关键字个数n m 1 说明该结点还有空位置 直接把关键字k插入到该结点的合适位置上 若该结点关键字个数n m 1 说明该结点已没有空位置 插入后需按以下方法把该结点分裂成两个结点 分配一新结点 把需分裂结点上的关键字从中间位置 即 m 2 处 分成两部分 左部分所含关键字放在旧结点中 右部分所含关键字放在新结点中 中间位置的关键字连同新结点的存储位置插入到父亲结点中 如果父结点的关键字个数也超过M 1 则要再分裂 再往上插 直至这个过程传到根结点为止 例1 关键字序列为 1 2 6 7 11 4 8 13 10 5 17 9 16 20 3 12 14 18 19 15 创建一棵5阶B 树 思考题 关键字序列为 35 43 11 27 18 39 78 53 64 47 99 创建一棵4阶B 树 B 树中关键字的删除 在B 树上删除关键字k的过程分两步完成 1 利用前述的B 树的查找算法找出该关键字所在的结点 2 在结点上删除关键字k分两种情况 一种是在叶子结点上删除关键字 另一种是在非叶子结点上删除关键字 B 树与B 树 例 对下图中的B 树 给出删除16 8 15 4等4个关键字的过程 1 10 2 3 6 2 13 16 2 1 2 2 4 5 3 7 8 9 2 11 12 2 14 15 4 17 18 19 20 B 树与B 树 在非叶子结点上删除关键字的过程 假设要删除关键字key i 在删去该关键字后 以该结点ptr i 所指子树中最小关键字key min 来代替被删关键字key i 所在的位置 然后再以指针ptr i 所指结点为根结点查找并删除key min 这样也就把再非叶子结点上删除关键字k的问题转化成了在叶子结点上删除关键字key min 的问题 B 树与B 树 n p0 k1 p1 k2 p2 ki Pi kn pn 在B 树的叶子结点上删除关键字共有以下三种情况 假如被删结点的关键字个数大于Min 说明删去该关键字后该结点仍满足B 树的定义 则可直接删去该关键字 B 树与B 树 假如被删结点的关键字个数等于Min 说明删去关键字后该结点将不满足B 树的定义 此时若该结点的左 或右 兄弟结点中关键字个数大于Min 则把该结点的左 或右 兄弟结点中最大 或最小 的关键字上移到双亲结点中 同时把双亲结点中大于 或小于 上移关键字的关键字下移到要删除关键字的结点中 这样删去关键字k后该结点以及它的左 或右 兄弟结点都仍旧满足B 树的定义 B 树与B 树 n p0 k1 p1 k2 p2 ki Pi kn pn 假如被删结点的关键字个数等于Min 并且该结点的左右兄弟结点中关键字个数均等于Min 这时 需把要删除关键字的结点与其左 或右 兄弟结点以及双亲结点中分割二者的关键字合并成一个结点 如果因此使双亲结点中关键字个数小于Min 则对此双亲结点作同样的处理 以致于可能直到对根结点作这样的处理而使整个树减少一层 B 树与B 树 B 树的概念 一棵B 树满足下列条件 1 每个分支结点至多有m棵子树 2 除根结点外 其他每个分支结点至少有 m 1 2 棵子树 3 根结点至少有两棵子树 至多有m棵子树 4 有n棵子树的结点有n个关键字 B 树与B 树 5 所有叶子结点包含全部 数据文件中记录 关键字及指向相应记录的指针 或存放数据文件分块后每块的最大关键字及指向该块的指针 而且叶子结点按关键字大小顺序链接 可以把每个叶子结点看成是一个基本索引块 它的指针不再指向另一级索引块 而是直接指向数据文件中的记录 6 所有分支结点 可看成是索引的索引 中仅包含它的各个子结点 即下级索引的索引块 中最大关键字及指向子结点的指针 B 树与B 树 B 树的结构特点 每个叶子结点中含有n个关键字和n个指向记录的指针 并且 所有叶子结点彼此链接构成一个有序链表 其头指针指向含有最小关键字的结点 每个分支结点中的关键字ki 即为其相应指针pi所指子树中关键字的最大值 所有叶子结点都在同一层上 每个叶子结点中关键字的个数均介于 m 2 和m之间 B 树与B 树 一棵4阶的B 树 B 树与B 树 5096 1550 3815 20264350 627896 5662 7178 848996 B 树的查找 在B 树中可以采用两种查找方式 一是直接从最小关键字开始进行顺序查找 另一种就是从B 树的根结点开始随即查找 这种查找方式与B 树的查找方法相似 只是在分支结点上的关键字与查找值相等时 查找并不结束 要继续查找叶子结点为止 此时若查找成功 则按所给指针取出对应记录即可 因此 在B 树中 不管查找成功与否 每次都是经过了一条从根结点到叶子结点的路径 B 树与B 树 5096 1550 3815 20264350 627896 5662 7178 848996 B 树与B 树 B 树中结点的插入 B 树的插入是从叶子结点开始 当插入后结点的关键字个数大于m时要分裂成两个结点 它们所含键值个数分别为 m