数据库索引技术

[e-mail]第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)