数据库索引技术new

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

1、高级数据库系统及其应用第2部分关系数据库系统实现第5章数据库索引技术xshxie@ustc.edu.cnLOGO第5章数据库索引技术5.1几种文件组织方式的特性对比分析5.2索引技术基础5.3B+树索引5.4散列索引5.5位图索引5.6多维空间索引2011年11月2日25.1几种文件组织方式的特性对比分析5.1.1文件的记录组织方式5.1.2各种文件组织方式的特性分析2011年11月2日35.1.1文件的记录组织方式堆文件(heapfile)排序文件(sortedfile)散列文件(hashedfi

2、le)以记录的某个属性值为参数，通过特定散列函数求得有限范围内的一个值作为记录的存储地址(即页地址或桶号)。用于计算散列的属性也称为散列键，它与搜索键具有类似的概念。2011年11月2日45.1.2各种文件组织方式的特性分析扫描假设文件有(Scan)B个数据页，每页有R个记录；平均等值搜索读写1个页的时间为(EqualitySearch)D，(CPU)处理一个记录的时间为取文件中满足等值选择条件的所有记录C。对于散列文件组织，散列函数映射的包含满足条件记录的所有页须从磁盘读到主存。时间为H。

3、范围搜索(RangingSearch)分析时采用如下简单代价模型：插入(insert)必须先定位新记录应插入的页，并将该页读入主存，I/O操作代价具有主导性。在主存页中完成插入修改，然后，再将该页写回磁盘。DB缓冲区大小对DB操作有重要影响。删除(delete)如采用等值或范围条件选择删除记录，则操作过程与为了行较全面的性能评价，分析时我们选择几种‘插入/范围搜索’操作类似；具有代表性的典型如直接给定删除记录DBrid操作，则可直接定位到记录所在页。：2011年11月2日55.1.2.

4、1堆文件的操作特性分析扫描－－操作代价为B(D+RC)等值搜索假设:满足条件的记录只有一个,平均需检查一半的页操作代价取0.5DB范围搜索－－必检查所有的页，操作代价B(D+RC)插入取文件的最后页到主存，插入后，再写回磁盘操作代价为2D+C删除不考虑记录被删除后的空间合并操作代价为：搜索时间＋C+D若已知rid，可直接定位到目标页，可省去搜索时间2011年11月2日65.1.2.2排序文件的操作特性分析扫描－－操作代价为B(D+RC)等值搜索假设：满足条件的记录只有一个可

5、用二分法搜索，操作代价取D*logB＋ClogR22若满足条件记录有多个，则该代价还应加上读取包含所有这些记录的若干个连续页。范围搜索－－等值搜索代价＋matches插入插入后，需进行排序调整，假设需调整约一半的记录插入操作的代价=等值搜索代价＋2*0.5B(D+RC)。删除如果等值或范围删除条件，则代价与插入操作相同若已知rid，可直接定位到目标页，可省去搜索时间2011年11月2日75.1.2.3散列文件的操作特性分析扫描－－页空间通常只保持约80%的占用率，扫描的实际操作代价取1.

6、25B(D+RC)等值搜索能非常有效支持等值选择假设满足条件的记录只有一条且相应桶中没有溢出页，则等值搜索操作代价仅为H+D+0.5RC范围搜索需要扫描所有的页，操作代价＝1.25B(D+RC)插入－－插入操作代价=等值搜索代价＋D+C。删除对等值或范围选择删除，代价=搜索代价＋D+C如果直接给定rid，则可省去搜索时间，代价=D+C2011年11月2日8各种文件组织方式的特性对比2011年11月2日95.2索引技术基础5.2.1索引技术综述5.2.2顺序索引及其特性5.2.3创建索引语

7、句2011年11月2日105.2.1索引技术综述索引是一种能帮助我们有效找出满足指定条件记录rid的辅助数据结构，是一种特殊类型的记录文件。索引记录常被称为索引项(indexentry)，简记为k*除了索引项按索引键值顺序组织的顺序索引外，也有按树结构(如B+树)和桶结构(散列)进行组织的索引。RDBMS中，索引项可能具有的三种形式（1）索引项k*是数据记录本身，无单独的索引文件。•这时数据文件可视为一种特殊的数据文件组织，即散列文件。（2），有独立的索引文件。（3）

8、rid-list>，有独立的索引文件，且每个索引项中允许包含多个rid。2011年11月2日115.2.1顺序索引及其特性聚集与非聚集索引聚集索引(clusteredindex)：指索引项的排序方式和数据文件记录排序方式一致的索引稠密索引与稀疏索引稠密索引：每个索引键值都对应有一索引项稀疏索引：只为某些搜索键值建立索引项多级索引为处理索引项过多带来的索引性能下降问题，可以将索引文本本身当作一般顺序数据文件，在其上