第5章 数据库索引技术

《第5章 数据库索引技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、xshxie@ustc.edu.cn第2部分关系数据库系统实现第5章数据库索引技术高级数据库系统及其应用第5章数据库索引技术几种文件组织方式的特性对比分析5.1索引技术基础5.2B+树索引5.3散列索引5.4位图索引5.5多维空间索引5.68/5/202125.1几种文件组织方式的特性对比分析5.1.1文件的记录组织方式5.1.2各种文件组织方式的特性分析8/5/202135.1.1文件的记录组织方式堆文件(heapfile)排序文件(sortedfile)散列文件(hashedfile)以记录的某个属性值为参数，通过特定

2、散列函数求得有限范围内的一个值作为记录的存储地址(即页地址或桶号)。用于计算散列的属性也称为散列键，它与搜索键具有类似的概念。8/5/202145.1.2各种文件组织方式的特性分析假设文件有B个数据页，每页有R个记录；平均读写1个页的时间为D，(CPU)处理一个记录的时间为C。对于散列文件组织，散列函数映射的时间为H。分析时采用如下简单代价模型：I/O操作代价具有主导性。DB缓冲区大小对DB操作有重要影响。为了行较全面的性能评价，分析时我们选择几种具有代表性的典型DB操作：扫描(Scan)等值搜索(EqualitySear

3、ch)取文件中满足等值选择条件的所有记录包含满足条件记录的所有页须从磁盘读到主存。范围搜索(RangingSearch)插入(insert)必须先定位新记录应插入的页，并将该页读入主存，在主存页中完成插入修改，然后，再将该页写回磁盘。删除(delete)如采用等值或范围条件选择删除记录，则操作过程与‘插入/范围搜索’操作类似；如直接给定删除记录rid，则可直接定位到记录所在页。8/5/202155.1.2.1堆文件的操作特性分析扫描－－操作代价为B(D+RC)等值搜索假设:满足条件的记录只有一个,平均需检查一半的页操作代价

4、取0.5DB范围搜索－－必检查所有的页，操作代价B(D+RC)插入取文件的最后页到主存，插入后，再写回磁盘操作代价为2D+C删除不考虑记录被删除后的空间合并操作代价为：搜索时间＋C+D若已知rid，可直接定位到目标页，可省去搜索时间8/5/202165.1.2.2排序文件的操作特性分析扫描－－操作代价为B(D+RC)等值搜索假设：满足条件的记录只有一个可用二分法搜索，操作代价取D*log2B＋Clog2R若满足条件记录有多个，则该代价还应加上读取包含所有这些记录的若干个连续页。范围搜索－－等值搜索代价＋matches插入插

5、入后，需进行排序调整，假设需调整约一半的记录插入操作的代价=等值搜索代价＋2*0.5B(D+RC)。删除如果等值或范围删除条件，则代价与插入操作相同若已知rid，可直接定位到目标页，可省去搜索时间8/5/202175.1.2.3散列文件的操作特性分析扫描－－页空间通常只保持约80%的占用率，扫描的实际操作代价取1.25B(D+RC)等值搜索能非常有效支持等值选择假设满足条件的记录只有一条且相应桶中没有溢出页，则等值搜索操作代价仅为H+D+0.5RC范围搜索需要扫描所有的页，操作代价＝1.25B(D+RC)插入－－插入操作代

6、价=等值搜索代价＋D+C。删除对等值或范围选择删除，代价=搜索代价＋D+C如果直接给定rid，则可省去搜索时间，代价=D+C8/5/20218各种文件组织方式的特性对比8/5/202195.2索引技术基础5.2.1索引技术综述5.2.2顺序索引及其特性5.2.3创建索引语句8/5/2021105.2.1索引技术综述索引是一种能帮助我们有效找出满足指定条件记录rid的辅助数据结构，是一种特殊类型的记录文件。索引记录常被称为索引项(indexentry)，简记为k*除了索引项按索引键值顺序组织的顺序索引外，也有按树结构(如B+

7、树)和桶结构(散列)进行组织的索引。RDBMS中，索引项可能具有的三种形式（1）索引项k*是数据记录本身，无单独的索引文件。这时数据文件可视为一种特殊的数据文件组织，即散列文件。（2），有独立的索引文件。（3），有独立的索引文件，且每个索引项中允许包含多个rid。8/5/2021115.2.1顺序索引及其特性聚集与非聚集索引聚集索引(clusteredindex)：指索引项的排序方式和数据文件记录排序方式一致的索引稠密索引与稀疏索引稠密索引：每个索引键值都对应有一索引项稀疏索引：只为某

8、些搜索键值建立索引项多级索引为处理索引项过多带来的索引性能下降问题，可以将索引文本本身当作一般顺序数据文件，在其上再建一个索引，即二级索引。如果建立三级或更多级的索引，通常不如直接使用B树方便。主索引与辅助索引仅当搜索键恰好是主码的索引时，索引称为主索引；8/5/202112稠密索引与稀疏索引应用示例8