高级数据库索引技术课件

高级数据库索引技术散列索引散列索引静态散列索引动态散列索引多维索引多维索引R树网格文件位图索引散列索引散列索引静态散列索引动态散列索引多维索引多维索引R树网格文件位图索引散列与散列函数散列函数选择要求:随机分布好、易计算；散列函数参数：查找键或散列键；基于散列的存储结构通常是每个散列值对应一个存储目标对象的桶(页/块)存储到桶的对象，既可能是实际数据项或数据记录，也可以是数据记录指针;散列索引散列索引静态散列索引动态散列索引多维索引多维索引R树网格文件位图索引散列函数形式：M=hash（k）散列函数条件：1、搜索码值的分布呈均匀分布2、记录的分布呈均匀分布静态散列索引54495450559553495350545158975349王悦王悦325350李丽李丽315449王永王永325450Ella365451李永李永295595杜华杜华425897王永王永405901武岳武岳395901桶0桶1桶1溢出桶各位数字之和与桶数模运算静态散列操作静态索引技术的特点：桶的数目是事先分配好的，且数目固定。其缺点是当索引文件发生变化时，桶数目无法改变。散列索引散列索引静态散列索引动态散列索引多维索引多维索引R树网格文件位图索引散列函数将这些键转换成的二进制位序列。因此，第一块有一个键被散列为0001的记录；而第二个块存放着键分别散列为1001和1100的记录。我们应该注意到图中每个存储块的“小方块”中都出现了数字1。这个数字其实出现在每个存储块的块头中，表明由散列函数得到的位序列中有多少位用于确定记录在该块中的成员资格。可扩展散列索引可扩展散列索引1.如果ji，那么不必对桶数组做什么变化。我们：a)将块B分裂成两个存储块。b)根据记录散列值的第（j+1）位，将B中记录分配到这两个存储块中，该位为0的记录保留在B中，而该位为1的记录则放入到新块中。c)把（j+1）存入这两个存储块的小方块中，以表明用于确定成员资格的二进制位数。d)调整桶数组中的指针，使原来指向块B的项指向块B或新块，这由项的第（j+1）位决定。可扩展散列索引操作可扩展散列索引操作如果j=i，那么我们必须先将i加1。我们使桶数组长度翻了一倍，因此数组中现在有2i+1个项。假定w是以前的桶数组中作为某项序号的i位二进制位序列。在新桶数组中，序号为w0和w1（即分别用0和1扩展w所得到的数）的项都指向原w项指向的块。也就是说，这两个新项共享同一个存储块，而存储块本身没有变化。该块的成员资格仍然按原先的位数确定。最后，我们继续像第一种情况中那样分裂B。动态散列索引优点：空间开销小，算法查询速度快，且与数据文件大小无关动态散列索引缺点：当桶数量增加时，其扩展的代价非常昂贵散列索引散列索引静态散列索引动态散列索引多维索引多维索引R树网格文件位图索引数据仓库的数据立方体地理信息系统(GIS)CAD/CAM系统多媒体信息处理多维空间索引的应用简介图图5.14数据仓库的数据立方体GIS被广泛用来处理各种空间数据，包括点、线、二维/三维-区域。例如，一幅地图中，可能同时包含小目标（点）、河流/公路（线），以及城市/湖泊（区域）等。地理信息系统(GIS)这类系统中通常要存储和处理大量的空间对象。类似GIS，这类系统中也必须存储和处理空间点/区域数据。范围查询和空间连接查询可能是这类应用中最常见的查询。CAM/CAD也是对象数据库系统发展的一个主要动因。CAD/CAM系统多媒体涵盖诸如图像、文本和各种类型时间序列数据（音频/视频）等各类对象，也需要空间管理方式。在多媒体数据库(multimedia databases)中，使用象“查找与特定对象相似的所有对象”这类相似查询可能极为普遍。多媒体信息处理散列索引散列索引静态散列索引动态散列索引多维索引多维索引R树网格文件位图索引R-树也是一种平衡树结构，其中被索引的多边形存储在叶节点上(这一点很象B+树)。每个树节点(叶节点/内节点)都对应有一个平行于坐标轴的矩形边界框。叶节点负责存储位于其内的所有被索引多边形，边界框是一个能涵盖其内所有存储对象的最小矩形。内节点存储其每个子节点的边界框和指向各子节点的指针。R树 R树叶子节点R树的两种视图例子：假设我要查询广州市天河区天河城附近一公里的所有餐厅地址怎么办？打开地图（也就是整个R树），先选择国内还是国外（也就是根结点）。然后选择华南地区（对应第一层结点），选择广州市（对应第二层结点），再选择天河区（对应第三层结点），最后选择天河城所在的那个区域（对应叶子结点，存放有最小矩形），遍历所有在此区域内的结点，看是否满足我们的要求即可。R树实例R树实例Function：Search描述：假设T为一棵R树的根结点，查找所有搜索矩形S覆盖的记录条目。S1:查找子树 如果T是非叶子结点，如果T所对应的矩形与S有重合，那么检查所有T中存储的条目，对于所有这些条目，使用Search操作作用在每一个条目所指向的子树的根结点上（即T结点的孩子结点）。S2:查找叶子结点 如果T是叶子结点，如果T所对应的矩形与S有重合，那么直接检查S所指向的所有记录条目。返回符合条件的记录。R树操作散列索引散列索引静态散列索引动态散列索引多维索引多维索引R树网格文件位图索引设有一个存放顾客购买金首饰记录的关系设有一个存放顾客购买金首饰记录的关系表表(age,salary)。为使问题简化，我们假设。为使问题简化，我们假设该关系只有顾客年龄和月薪两个属性。该关系只有顾客年龄和月薪两个属性。-实例数据中有12个顾客，相关记录被表示成下列的年龄-薪水对：(26,0.6)(45,0.6)(51,0.75)(51,1)(51,1.28)(70,1.30)(85,1.4)(30,2.6)(26,4.0)(45,3.5)(51,2.75)(60,2.6)特定查询：根据坐标找到数据块部分匹配查询：最近邻查询一个特定点P，找到P的桶，然后查找与P点有一定距离的L的点。散列索引散列索引静态散列索引动态散列索引多维索引多维索引R树网格文件位图索引位图的优点：减少即席查询的相应时间。和其它类型索引比较，真正节约了索引数据空间。即使在非常差的硬件上，也可能会有戏剧化的性能提升。可以通过位图索引直接计数。位图索引的缺点如果有比较频繁的insert,update等操作，导致性能很低可能会溢出，索引数据块难于放下整个索引值，这导致低效。谢谢 谢！谢！