华南理工大学数据结构chapter10.pptVIP

* B+-Tree Space Analysis (1) Example: Consider a B+-Tree of order 100 with leaf nodes containing 100 records. 1 level B+-tree: Min 0, Max 100 2 level B+-tree: Min: 2 leaves of 50 for 100 records. Max: 100 leaves with 100 for 10,000 records. 3 level B+-tree: Min: 2 x 50 nodes of leaves, each leaf of 50 records for 5000 records. Max: 1003 = 1,000,000 records. 4 level B+-tree: Min: 250,000 records (2 * 50 * 50 * 50). Max: 1004 = 100 million records. * B+-Tree Space Analysis (2) Ways to reduce the number of disk fetches: Keep the upper levels in memory. Manage B+-Tree pages with a buffer pool. * B树 (1) 1. B-树定义 B-树是一种平衡的多路查找树，它在文件系统中很有用。 定义：一棵m 阶的B-树，或者为空树，或为满足下列特性的m 叉树：⑴ 树中每个结点至多有m 棵子树；⑵ 若根结点不是叶子结点，则至少有两棵子树； ⑶ 除根结点之外的所有非终端结点至少有?m/2?棵子树；⑷ 所有的非终端结点中包含以下信息数据： ??????（A0，K1，A1，K2，…，Kn，An）其中：Ki（i=1,2,…,n）为关键码，且KiKi+1， ???????????Ai?为指向子树根结点的指针(i=0,1,…,n)，且指针Ai-1 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn. ???????????n?为关键码的个数。⑸ 所有的叶子结点都出现在同一层次上，即所有叶节点具有相同的深度，等于树高度。 * B树 (2) 2 . B-树的查找 B-树的查找类似二叉排序树的查找，所不同的是B-树每个结点上是多关键码的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功；否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码。 3. B-树主要应用在文件系统 为了将大型数据库文件存储在硬盘上 以减少访问硬盘次数为目的在此提出了一种平衡多路查找树——B-树结构，成为文件系统的一种标准，由其性能分析可知它的检索效率是相当高的 为了提高?B-树性能，还有很多种B-树的变型，力图对B-树进行改进。 * B+树 1 . ?B+树是应文件系统所需而产生的一种B-树的变形树。 一棵m 阶的B+树： ⑴ 有n 棵子树的结点中含有n 个关键码； ⑵ 所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且叶子结点本身依关键码的大小自小而大的顺序链接。 ⑶ 所有的内部结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。 2. 通常在B+树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点。因此可以对B+树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根节点开始，进行随机查找。? 3. 在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找时，若内部结点上的关键码等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。 目前大部分数据库系统及文件系统都采用B+Tree或其变种作为索引结构。? * * Entry sequenced files are not practical as an organization for large databases * * A linear index is good for indexing an entry sequenced file. * Second level index stores the first key for each disk page. * * * * Second fi