【教学课件】第五章索引技术.ppt
《【教学课件】第五章索引技术.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第五章索引技术.ppt(32页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第五章第五章 索引技术索引技术DBMS回答用户查询时的检索操作包括三个要素:输入输入:用户要求(如关键字)搜索搜索:寻找,检查(匹配关键字),定位。输出输出:用户所需信息。搜索的效率依赖于被搜索空间的大小和被搜索对象的组织结构。搜索的效率 索引的基本思想是以搜索较小的排序集 (关键字,记录地址)去代替搜索较大的主数据集合。从而提高了检索效率。散列(Hash)通过把关键码值映射到表中的某个位置来访问记录的过程称为散列。大多数散列方法根据计算出的地址来放置记录,而不需根据关键码值的顺序来放置。解决冲突的技术可以分为两类:开散列方法(也称为拉链法)和闭散列方法(也称为开地址方法)。这两种方法的不同之
2、处在与将冲突记录是存储在表外(开散列)还是存储在表内另一个槽内(闭散列)。有7个数的开散列方法 无序索引 索引映射:关键字-记录号。索引文件本身不排序。平均搜索次数为关键字总数/2,主文件都是排序的。那么,隔N项抽出一项而建立起来的。索引集合就缩小到原来文件的1/N。其定位误差小于N。然后在N个项中线性搜索。稀索引线性索引线性索引 线性索引是一个按关键码/指针顺序组织的索引文件。这个文件按照关键码的顺序进行排序。指针指向磁盘中完整记录的位置。倒排表 考虑一个有关职工记录的大型数据库。如果主关键码是职工的标识号,次关键码是职工的名字,那么名字索引中的每一条记录都把名字与一个或多个标识号关联起来。
3、这样组织起来的次关键码索引称为倒排表或称为倒排文件。它把检索反过来进行,从次关键码到主关键码,再到实际数据记录。它也被称为一个表,因为每个次关键码值有一组主关键码值与之相关联。一个倒排表的结构B树树一棵m阶的B树,或为空树,或为满足下列特性的m叉树:1)树中每个节点至多有m棵子树;2)若根节点不是叶子节点,则至少有两棵子树;3)除根之外的所有非叶子节点至少有m/2棵子树;4)所有的非叶子节点中包含下列信息 (n,A0,K1,A1,K2,A2,.,Kn,An)其中:Ki(i=1,.,n)为关键字,且KiKi+1(i=1,.,n-1);Ai(i=0,.,n)为指向子树根节点的指针,且指针Ai-1所
4、指子树中所有节点的关键字均小于Ki(i=1,.,n),An所指子树中所有节点的关键字均大于Kn,n(m/2 1=m-1)为关键字的个数.5)树中所有叶节点都出现在同一层上。B树树例B树中由小到大的结构层次是:索引项节点树。l索引项结构索引项的结构可表示如下:struct IdxItemStruct /*索引项的结构,长64字节*/long N;/*记录号,长4字节*/long A;/*索引项的右儿子指针,4字节*/long K;/*关键字K,56字节*/;typedef struct IdxItemStruct IdxItem;/*索引类别名*/l节点结构struct NodeStruct i
5、nt ItesOnNode;/*节点上实际项数*/long A0;/*节点的左儿子指针*/IdxItem IAMaxItem;/*索引项数组*/;B树的三大特点树的三大特点1.平衡性。在动态活动(查、删、改、重建)中,始终保持了平衡,即从任一个叶节点到根的路径一样长。B树正是得名于平衡(balanced)。平衡性保证了1搜索步数B树高度。从而避免了搜索效率因记录而异引起的“贫富不均”。2.过半性。除了根节点外(它至少有一个索引项),其余的节点上装载因子永远过半。保证了在非根节点上 最大项数/2实有项数最大项数 3.顺序性。在动态活动中,始终左小右大。对于每个索引项,处于该项左边的项及左边的一切
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教学课件 教学 课件 第五 索引 技术
限制150内