B 树-课件（PPT-精）.pptVIP

1 B_树 B_树主要用于文件系统中，在B_树中，每个结点的大小为一个磁盘页，结点中所包含的关键字及其孩子的数目取决于页的大小。一棵度为m的B_树称为m阶B_树，其定义是： 一棵m阶B_树，或者是空树，或者是满足以下性质的m叉树： ⑴ 根结点或者是叶子，或者至少有两棵子树，至多有m棵子树； ⑵ 除根结点外，所有非终端结点至少有?m/2?棵子树，至多有m棵子树； ⑶ 所有叶子结点都在树的同一层上； ⑷ 每个结点应包含如下信息： (n，A0，K1，A1，K2，A2，… ，Kn，An) 其中Ki(1≤i≤n)是关键字，且KiKi+1 (1≤i≤n-1)；Ai(i=0，1，… ，n)为指向孩子结点的指针，且Ai-1所指向的子树中所有结点的关键字都小于Ki ，Ai所指向的子树中所有结点的关键字都大于Ki ；n是结点中关键字的个数，且?m/2?-1≤n≤m-1，n+1为子树的棵数。 当然，在实际应用中每个结点中还应包含n个指向每个关键字的记录指针，如图9-13是一棵包含13个关键字的4阶B_树。 ⑵ 结点“分裂”方法 设待“分裂”结点包含信息为： (m，A0，K1，A1，K2，A2，… ，Km，Am)，从其中间位置分为两个结点： (?m/2?-1，A0，K1，A1，… ，K?m/2?-1 ，A?m/2?-1 ) (m-?m/2?，A?m/2?，K?m/2?+1，A?m/2?+1 ，… ，Km，Am ) 并将中间关键字K?m/2?插入到p的父结点中，以分裂后的两个结点作为中间关键字K?m/2?的两个子结点。 当将中间关键字K?m/2?插入到p的父结点后，父结点也可能不满足m阶B_树的要求(分枝数大于m)，则必须对父结点进行“分裂”，一直进行下去，直到没有父结点或分裂后的父结点满足m阶B_树的要求。 2 B+树 在实际的文件系统中，基本上不使用B_树，而是使用B_树的一种变体，称为m阶B+树。 它与B_树的主要不同是叶子结点中存储记录。在B+树中，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键字”，用来界定某一关键字的记录所在的子树。一棵m阶B+树与m阶B_树的主要差异是： ⑴ 若一个结点有n棵子树，则必含有n个关键字； ⑵ 所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接； ⑶ 所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大(或最小)关键字。 如图9-16是一棵3阶B+树。 由于B+树的叶子结点和非叶子结点结构上的显著区别，因此需要一个标志域加以区分，结点结构定义如下： B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 B+树插入 3 B*树 节点分裂比较 www. B+树的分裂 当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针 B*树的分裂 当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针 管理信息系统 江汉大学商学院 * B+树 掌握B-树、B+树和B*树的基本定义、结构及操作 重点掌握B+树和B*树的插入操作及节点分裂 B-树 B+树 B*树 教学目的 主要内容 g f e d c b a 1 24 1 15 1 ∧ 20 ∧ 2 ∧ 28 ∧ 31 ∧ 2 ∧ 10 ∧ 20 ∧ 1 ∧ 56 ∧ 1 ∧ 50 ∧ 1 ∧ 37 ∧ 3 33 48 53 i h 图9-13 一棵包含13个关键字的4阶B_树 f h m b (a) 一棵2-3树 f h m b d (b) 插入d后 f h m p b d 分裂 (c) 插入p后并进行分裂 h f m b d p h l f m b d p (d) 插入l后 分裂 g h l f m b d p (e) 插入g后并进行分裂 l f h m b d p p 分裂 图9-14 在B_树中进行插入的过程 l f h m b d p g l b d p