东南大学数据结构_Lec012讲述.pptx

第12讲 多路查找树、哈希表 B-树和B+树 哈希表 1 数据结构 树形索引表 平衡二叉排序树便于动态查找，因此用平衡二叉排序树来组织索引表是一种可行的选择。当用于大型数据库时，所有数据及索引都存储在外存，因此，涉及到内、外存之间频繁的数据交换，这种交换速度的快慢成为制约动态查找的瓶颈。 若以二叉树的结点作为内、外存之间数据交换单位，则查找给定关键字时对磁盘平均进行(㏒2n)次访问是不能容忍的，因此，必须选择一种能尽可能降低磁盘I/O次数的索引组织方式。树结点的大小尽可能地接近页的大小。 R.Bayer和E.Mc Creight在1972年提出了一种多路平衡查找树，称为B-树(其变型体是B+树)。 数据结构 2 B-树的概念 一棵m阶的B-树，或为空树，或为满足下列特性的m叉树： 树中每个结点至多有m棵子树； 若根结点不是叶子结点，则至少有两棵子树； 除根之外的所有非终端结点至少有?m/2?棵子树； 所有的非终端结点中包含下列信息数据 (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 (1≤i≤n)，An所指子树中所有结点的关键字均大于Kn；n( ?m/2? -1≤n≤m-1)为关键字的个数（或n+1为子树个数）。 所有的叶子结点都出现在同一层次上，并且不带信息。 数据结构 3 B-树的结构 条件(1)和(3)使每个结点至少半满； 条件(2) 使B-树不至于一开始就偏向一边； 条件(4) 结点中关键字递增排列，使B-树具有某种“中序”递增性，可看成二叉排序树的扩充，是一种平衡多叉排序树；而子树数比关键字个数多1，使得最终叶子数比树中所含关键字数多1。 条件(5) 叶子都在同一层，使B-树高度上平衡；而叶子不含关键字，表示叶子实际上是树中并不存在的外部结点，且指向这些外部结点的指针为空； 数据结构 4 B-树的结点类型定义 根据m阶B-树的定义，结点类型定义如下： #define M 5 /* 根据实际需要定义B_树的阶数 */ typedef struct BTNode { int keynum ; /* 结点中关键字的个数 */ KeyType key[M+1] ; /* 关键字向量,key[0]未用 */ RecType *recptr[M+1] ; /* 记录指针向量，recptr[0]未用 */ struct BTNode *parent ; /* 指向父结点的指针 */ struct BTNode *ptr[M+1] ; /* 子树指针向量 */ } BTNode; 数据结构 5 B-树的查找过程 数据结构 6 在B-树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程。 例：查找26 　　查找100 类似二叉排序树的查找 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96 B-树查找分析 两种基本操作 在B-树中找结点 B-树通常存储在磁盘上，第1步查找操作在磁盘上进行。 在结点中找关键字 在磁盘上找到指针p所指结点后，先将结点中的信息读入内存，因此，第2步查找操作在内存中进行；然后再利用顺序查找或折半查找查询等于给定值的关键字。 由于访外（磁盘）耗时，在磁盘上进行查找的次数，即待查关键字所在结点在B-树上的层次数，是决定B-树查找效率的首要因素。 数据结构 7 B-树查找分析 考虑最坏的情况，即待查结点在B-树的最大层次上。 含N个关键字的m阶B-树的最大深度是多少？ 根据B-树的定义： 第一层至少有1个结点；第二层至少有2个结点； 由于除根之外的每个非终端结点至少有?m/2?棵子树，则第三层至少有2(?m/2?)个结点；… ； 依次类推，第l+1层至少有2(?m/2?) l?1个结点，而l+1层的结点为叶子结点。 若m阶B-树中具有N个关键字，则叶子结点即查找不成功的结点为N+1，由此有： N+l ≥ 2*(?m/2? ) l?1 反之 l ≤ log ?m/2? ((N+1)/2) + 1 数据结构 8 结论：在含有N个关键字的B-树上进行查找时，从根结点到关键字所在结点的路径上涉及