【教学课件】第五章索引技术.ppt
第五章第五章 索引技术索引技术DBMS回答用户查询时的检索操作包括三个要素：输入输入：用户要求（如关键字）搜索搜索：寻找，检查（匹配关键字），定位。输出输出：用户所需信息。搜索的效率依赖于被搜索空间的大小和被搜索对象的组织结构。搜索的效率 索引的基本思想是以搜索较小的排序集 （关键字，记录地址）去代替搜索较大的主数据集合。从而提高了检索效率。散列(Hash)通过把关键码值映射到表中的某个位置来访问记录的过程称为散列。大多数散列方法根据计算出的地址来放置记录，而不需根据关键码值的顺序来放置。解决冲突的技术可以分为两类：开散列方法（也称为拉链法）和闭散列方法（也称为开地址方法）。这两种方法的不同之处在与将冲突记录是存储在表外（开散列）还是存储在表内另一个槽内（闭散列）。有7个数的开散列方法 无序索引 索引映射:关键字-记录号。索引文件本身不排序。平均搜索次数为关键字总数/2,主文件都是排序的。那么，隔N项抽出一项而建立起来的。索引集合就缩小到原来文件的1/N。其定位误差小于N。然后在N个项中线性搜索。稀索引线性索引线性索引 线性索引是一个按关键码/指针顺序组织的索引文件。这个文件按照关键码的顺序进行排序。指针指向磁盘中完整记录的位置。倒排表 考虑一个有关职工记录的大型数据库。如果主关键码是职工的标识号，次关键码是职工的名字，那么名字索引中的每一条记录都把名字与一个或多个标识号关联起来。这样组织起来的次关键码索引称为倒排表或称为倒排文件。它把检索反过来进行，从次关键码到主关键码，再到实际数据记录。它也被称为一个表，因为每个次关键码值有一组主关键码值与之相关联。一个倒排表的结构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所指子树中所有节点的关键字均小于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 int ItesOnNode;/*节点上实际项数*/long A0;/*节点的左儿子指针*/IdxItem IAMaxItem;/*索引项数组*/;B树的三大特点树的三大特点1.平衡性。在动态活动（查、删、改、重建）中，始终保持了平衡，即从任一个叶节点到根的路径一样长。B树正是得名于平衡（balanced）。平衡性保证了1搜索步数B树高度。从而避免了搜索效率因记录而异引起的“贫富不均”。2.过半性。除了根节点外（它至少有一个索引项），其余的节点上装载因子永远过半。保证了在非根节点上 最大项数/2实有项数最大项数 3.顺序性。在动态活动中，始终左小右大。对于每个索引项，处于该项左边的项及左边的一切子树中最大关键字本关键字右边的项及右边的一切子树中最小关键字。顺序性保证了在搜索时，可通过比较而确定下一步的搜索方向。B树的价值在于动态性能好。多维索引技术多维索引技术我们考虑两种多维应用问题:地理信息系统地理信息系统一个地理信息系统存储二维空间中的对象。通常这些数据库中存储的对象包括房屋，道路，桥梁，管道和其它实物.立体数据系统 它将数据看作是处于一个高维空间中。许多公司收集多维数据以支持决策支持系统类型的应用，他们分析各种销售信息以更好的理解公司的运作。比如，一个连锁店可以记录每一笔买卖，其中包括如下信息：l日期和时间l商店名l所购物品名l物品的颜色l物品的尺寸也许还有其它一些信息。查询关于在二维空间中的一组点的最近邻居。我们可以用一对实数来描述点Points(x,y)，也就是说，用两个实数来描述点的两个坐标。假设我们要求距离（10.0，20.0）最近的那个点。SQL中的多维查询中的多维查询 SELECT *FROM POINTS P WHERE NOT EXISTS(SELECT*FROMPOINTS WHERE(x-10.0)*（x-10.0）+（y-20.0）*（y-20.0）value)return rt;/Found itelse if(dkey(val,lev)value,lev)return Kdfindhelp(rt-left,val,(lev+1)%K,K);else return Kdfindhelp(rt-right,val,(lev+1)%K,K);R-R-树树 R树吸收了B树的一些特点，是用来表示多维数据的一种数据结构。一棵R树表示一个区域，R树的每个内部结点对应着它内部的一个子区域。理论上，这些区域可以是任何形状的，但为了实现上的方便，通常将它们定义成矩形。一棵R树的根结点中记录着表示相应矩形区域的左下和右上两顶点的坐标。同样，R树的每个子结点中记录着表示相应矩形区域的左下和右上两顶点的坐标。对应的R树结构R树结构中的三个层次:R树中由小到大的结构层次是：索引项节点树。l索引项结构索引项的结构可表示如下：struct IdxItemStruct /*索引项的结构*/long A;/*索引项的儿子指针*/int x1;int y1;/*儿子指针所指矩形区域的 左下角及右上角二点坐标值*/int x2;int y2 ;typedef struct IdxItemStruct IdxItem;/*索引类别名*/l节点结构struct NodeStruct int ItesOnNode;/*节点上实际项数*/IdxItem IAMaxItem;/*索引项数组*/;一种典型的R树查询就是“我在哪？”这个查询可找到一特定的点P和该点所在的区域（或数据区域）之间的关系。我们可以从查找根结点的每个孩子开始，找到包含P的相应区域（注意：可能这样的区域有一个或很多个，也可能一个也没有）。假如我们找不到这样的区域，那么查找过程就结束，点P不在任何区域内，如果找到至少一个包含P的区域，那么我们必须查找每一个这样的结点的孩子结点。当查询到达一个或多个叶子时，我们便可找到一些实际的数据区域，它们是一些由指针指向的完整的记录。R树查询 如果要插入一个新区域P（包含实体P）到R树中，可以从根结点开始寻找适合条件的子区域。假如有多个满足这一条件的区域，那么选择其中的一个，到达相应的子结点，然后再从这个子结点开始重复这样的过程。假如找不到这样的子区域可包含区域P，那么我们就必须扩大其中的某个子区域.一般来说，我们只想对某个区域的扩大程度变得很小，因此可以找这样的一个子区域：对它进行最少的扩展便可包含区域P，然后改变此区域的大小直到可以包含P，然后把P插入其子结点。R R树上的操作树上的操作(1)(1)假如此结点中的区域数超过规定，就必须分裂这个叶子结点。怎样分裂又是一个大问题。一般来说，我们要求分裂成的这两个子区域越小越好,但又要求它们能覆盖原结点所表示的数据区域。分裂之后必须保证在它们的父结点中有相应的区域包含它们和相应的指针指向它们。如果在父结点中有空位置可以插入这样的区域，那么操作便结束。这和B树从叶子到根进行分裂的情况相似。R R树上的操作树上的操作(2)(2)增加一个天线点。这个天线点落在A区域内。因为，所有节点最多含4个子节点。所以，A节点必须分裂在二个子结点中。同样，当删除空间对象时，会引起R树的合并。分裂后的R树作业实现R树程序.(所用语言,平台不限.)
