LOGOxshxie@ustc.edu.cn第2部分关系数据库系统实现第5章数据库索引技术高级数据库系统及其应用2011年11月2日2第5章数据库索引技术几种文件组织方式的特性对比分析5.1索引技术基础5.2B+树索引5.3散列索引5.4位图索引5.5多维空间索引5.62011年11月2日35.1几种文件组织方式的特性对比分析5.1.1文件的记录组织方式5.1.2各种文件组织方式的特性分析2011年11月2日45.1.1文件的记录组织方式堆文件(heapfile)排序文件(sortedfile)散列文件(hashedfile)以记录的某个属性值为参数,通过特定散列函数求得有限范围内的一个值作为记录的存储地址(即页地址或桶号)。用于计算散列的属性也称为散列键,它与搜索键具有类似的概念。2011年11月2日55.1.2各种文件组织方式的特性分析假设文件有B个数据页,每页有R个记录;平均读写1个页的时间为D,(CPU)处理一个记录的时间为C。对于散列文件组织,散列函数映射的时间为H。分析时采用如下简单代价模型:I/O操作代价具有主导性。DB缓冲区大小对DB操作有重要影响。为了行较全面的性能评价,分析时我们选择几种具有代表性的典型DB操作:扫描(Scan)等值搜索(EqualitySearch)取文件中满足等值选择条件的所有记录包含满足条件记录的所有页须从磁盘读到主存。范围搜索(RangingSearch)插入(insert)必须先定位新记录应插入的页,并将该页读入主存,在主存页中完成插入修改,然后,再将该页写回磁盘。删除(delete)如采用等值或范围条件选择删除记录,则操作过程与‘插入/范围搜索’操作类似;如直接给定删除记录rid,则可直接定位到记录所在页。2011年11月2日65.1.2.1堆文件的操作特性分析扫描--操作代价为B(D+RC)等值搜索假设:满足条件的记录只有一个,平均需检查一半的页操作代价取0.5DB范围搜索--必检查所有的页,操作代价B(D+RC)插入取文件的昀后页到主存,插入后,再写回磁盘操作代价为2D+C删除不考虑记录被删除后的空间合并操作代价为:搜索时间+C+D若已知rid,可直接定位到目标页,可省去搜索时间2011年11月2日75.1.2.2排序文件的操作特性分析扫描--操作代价为B(D+RC)等值搜索假设:满足条件的记录只有一个可用二分法搜索,操作代价取D*log2B+Clog2R若满足条件记录有多个,则该代价还应加上读取包含所有这些记录的若干个连续页。范围搜索--等值搜索代价+matches插入插入后,需进行排序调整,假设需调整约一半的记录插入操作的代价=等值搜索代价+2*0.5B(D+RC)。删除如果等值或范围删除条件,则代价与插入操作相同若已知rid,可直接定位到目标页,可省去搜索时间2011年11月2日85.1.2.3散列文件的操作特性分析扫描--页空间通常只保持约80%的占用率,扫描的实际操作代价取1.25B(D+RC)等值搜索能非常有效支持等值选择假设满足条件的记录只有一条且相应桶中没有溢出页,则等值搜索操作代价仅为H+D+0.5RC范围搜索需要扫描所有的页,操作代价=1.25B(D+RC)插入--插入操作代价=等值搜索代价+D+C。删除对等值或范围选择删除,代价=搜索代价+D+C如果直接给定rid,则可省去搜索时间,代价=D+C2011年11月2日9各种文件组织方式的特性对比2011年11月2日105.2索引技术基础5.2.1索引技术综述5.2.2顺序索引及其特性5.2.3创建索引语句2011年11月2日115.2.1索引技术综述索引是一种能帮助我们有效找出满足指定条件记录rid的辅助数据结构,是一种特殊类型的记录文件。索引记录常被称为索引项(indexentry),简记为k*除了索引项按索引键值顺序组织的顺序索引外,也有按树结构(如B+树)和桶结构(散列)进行组织的索引。RDBMS中,索引项可能具有的三种形式(1)索引项k*是数据记录本身,无单独的索引文件。•这时数据文件可视为一种特殊的数据文件组织,即散列文件。(2)k,rid,有独立的索引文件。(3)k,rid-list,有独立的索引文件,且每个索引项中允许包含多个rid。2011年11月2日125.2.1顺序索引及其特性聚集与非聚集索引聚集索引(clusteredindex):指索引项的排序方式和数据文件记录排序方式一致的索引稠密索引与稀疏索引稠密索引:每个索引键值都对应有一索引项稀疏索引:只为某些搜索键值建立索引项多级索引为处理索引项过多带来的索引性能下降问题,可以将索引文本本身当作一般顺序数据文件,在其上再建一个索引,即二级索引。如果建立三级或更多级的索引,通常不如直接使用B树方便。主索引与辅助索引仅当搜索键恰好是主码的索引时,索引称为主索引;2011年11月2日13稠密索引与稀疏索引应用示例2011年11月2日14多级索引应用示例2011年11月2日15一种带有间接桶层的辅助索引结构2011年11月2日165.3B+树5.3.1B+树概述5.3.2B+树操作5.3.3B+树的效率与实用化2011年11月2日175.3.1B+树特点及约束(1)B+树的基本特点是传统B树的一种增强结构。采用一种平衡树来组织索引项。内节点用于搜索导向,叶节点用来存储数据项。是一种动态的索引结构,其树大小会因数据项的多少而动态地增长或收缩。每个树节点用一个页来存储。树操作(插入/删除)能保持树平衡。从根节点到任一个叶节点路径都是等长的。B+树的阶数(通常以字母m表示)指B+树中节点允许容纳的昀大索引键值个数。2011年11月2日185.3.1B+树特点及约束(2)根节点/内节点格式化除了根节点外,所有树节点都必须保持50%的占用率(即半满)。一个含有j个索引键值的节点,必含有j+1个指针•节点内容格式“p0,K1,p1,…,Kj,pj”,其中,指针pi指向一个键值k落在Ki≤nKi+1范围的子树。m阶B+树的非叶节点至多只能有m+1个子节点;•内节点至少要有m/2+1个子节点;•根节点至少要有2个子节点叶节点格式化至多包含m个数据项,至少包含(m+1)/2个数据项;每个项既可以直接存放实际数据记录,也可以是形式为K,rid|pid指针(简记为k*)的数据记录指针。每个叶子节点与前后的叶子节点用双链连接在一起。2011年11月2日195.3.2.1B+树搜索算法(算法5.1)//主函数funcfind(search-key-valueK)returnsnodePointer//给定搜索键值K,找所在的叶节点returntree-search(root,K);endfunc2011年11月2日20B+树搜索算法(算法5.1)2011年11月2日21一个阶数m=4的B+树及其搜索示例2011年11月2日225.3.2.2B+树插入算法(算法5.2)2011年11月2日23B+树插入算法(到达叶节点后的处理逻辑)2011年11月2日24B+树插入算法(非叶节点中分裂子节点处理逻辑)2011年11月2日25插入算法应用示例演示2011年11月2日265.3.2.3B+树删除算法(算法5.3)2011年11月2日27B+树删除算法(到达叶节点后的处理逻辑)2011年11月2日28B+树删除算法(处理有子节点被删除逻辑)2011年11月2日29删除算法应用示例演示2011年11月2日305.3.3B树的效率与实用化B+树索引的优势虽然B+树付出了在内节点存储索引项的开销,但能获得排序文件的所有好处,且还能保持很好的插入、删除性能。B+树没有溢出页;实用条件下,B+树的每个页能容纳搜索键数可能很大,分裂/合并树节点的情况可能很少发生。按索引键值检索一条记录,典型只需要2~3次磁盘I/O。2011年11月2日315.3.3B树的效率与实用化B+树索引的优势B+树重复键问题及其处理当重复键很多时,可能会出现叶节点无法容纳具有给定键值所有记录项的情况。常用处理方法•用溢出页来处理重复键值问题。•把重复键按一般非重复键一样处理,这时重复键项将出现在一个或连续的多个页节点中。•将rid值也作为搜索键的一个部分,这实际上相当于消除了重复键。2011年11月2日325.3.3B树的效率与实用化B+树索引的优势B+树重复键问题及其处理键值压缩处理(键压缩)如果搜索键值很长,页中能存储的索引项数就很少,树的宽度(fan-out)也就小。昀大化fan-out以减小树的深度,对减少树操作磁盘I/O数非常重要。键值压缩原理•只保留键的前缀。•为确保能保持一个索引项中键值的比较语义,在压缩一个项时,除考虑它相邻项键值外,还要考虑左、右子树中的昀大键值。2011年11月2日335.3.3.3批量加载数据集到B+树数据项加入到B+树索引可能会遇到两种情形:拟加入的数据记录集之前已建有B+树索引。这时,可利用标准的B+树插入算法,将数据项逐个加入数据集,同时更新相应的B+树索引。拟加入的数据集上还没有B+树索引。对于后者,为减少操作代价,常采用批量加载方法实现批量加载数据集到B+树的算法步参见书本,P1592011年11月2日34图5.6批量加载B+树过程演示2011年11月2日35批量加载数据集到B+树的代价分析这个操作算法可归纳为三大步骤:第一步,从一个记录集创建要插入到索引的数据项;•该步包括扫描关系记录集,并生成和写出相应的数据项。•其代价为(R+E)次I/Os–R是记录集数据文件的总页数,E是包含数据项的总页数。第二步,排序数据项;•外部排序含数据项的有E个页,保守估计需要3E次I/Os(参见6.1部分)。第三步,从排序好的数据项中建立B+树索引。•该步的代价只是写出所有索引页的代价。总代价为:R+4E+(B树索引节点数)2011年11月2日365.4散列索引5.4.1静态散列存储表5.4.2可扩展的动态散列5.4.3线性散列表2011年11月2日37散列存储技术概要散列与散列函数散列函数选择要求:随机分布好、易计算;散列函数参数:查找键或散列键;函数值:散列值基于散列的存储结构通常是每个散列值对应一个存储目标对象的桶(页/块)•散列值对应桶编号(如果散列值范围是0~B-1,则桶总数为B)。•根据被散列对象键值,计算散列值,然后保存到相应的桶中;•当桶内对象不止一个时,按链连接起来,构成对象链。存储到桶的对象,既可能是实际数据项或数据记录,也可以是数据记录指针;2011年11月2日38也称为辅存散列表;桶数目固定,不随对象插入和删除变化;桶中直接存放数据记录;插入新项时,如果空间不够(桶溢出)属于同一个桶的多个页构成溢出页链;桶内对象被删除,桶溢出页变为空时,也应将空溢出页删除。辅存散列的效率理想情况只需一次I/O;非理想情况可能需要多次I/O(因存在对象链、溢出块链等情况)。5.4.1静态散列存储表2011年11月2日395.4.2可扩展的动态散列(1)静态散列一般通过增加溢出页来处理溢出问题。如不希望增加溢出页,也可修改散列函数,将桶的数目扩大(如扩大一倍),然后重组数据文件。但这种重组的代价可能很大:•需要读入n个页,并写回2n个页。克服这个问题的一个方法引入一个仅存储桶指针的目录数组,用翻倍目录数组来取代翻倍数据桶数目;•由于每个目录项只含有一个桶指针,目录所需存储页一般很少,这样翻倍的代价就很小。每次只分裂有溢出的桶。2011年11月2日405.4.2可扩展的动态散列(2)引入一散列函数h,将索引键值映射为二进制数,并解释昀后的d个比特位。d值是目录项的编码位数目录项总数为2d个;d值加1目录项数将增加一倍。d值也称全局位深度(theglobalbit-depth)