《4 索引结构》由会员分享，可在线阅读，更多相关《4 索引结构（79页珍藏版）》请在金锄头文库上搜索。
1、索引结构索引结构 n n 索引结构基础索引结构基础 n n B+B+树索引树索引 n n 散列索引散列索引 n n 多维索引多维索引 /791 数据存取路径数据存取路径 支持对于所要求的数据进行快速定位的附支持对于所要求的数据进行快速定位的附 加的数据结构。加的数据结构。 每个索引结构有一个特定的搜索码与之关每个索引结构有一个特定的搜索码与之关 联。索引按一定的方式存储搜索码的值，并将联。索引按一定的方式存储搜索码的值，并将 搜索码与包含该搜索码的记录关联起来。搜索码与包含该搜索码的记录关联起来。 搜索码：用于在文件中查找记录的属性或搜索码：用于在文件中查找记录的属性或 属性集。属性集。 se
2、arch-keypointer /792 Index Evaluation MetricsIndex Evaluation Metrics n n Access types supported efficiently. E.g., Access types supported efficiently. E.g., nrecords with a specified value in the attribute nor records with an attribute value falling in a specified range of values. n n Access timeAc
3、cess time n n Insertion timeInsertion time n n Deletion timeDeletion time n n Space overheadSpace overhead /793 基本索引结构基本索引结构 两种基本的索引：两种基本的索引： n n 顺序索引。索引基于对值的一种排序。顺序索引。索引基于对值的一种排序。 （最常用的是（最常用的是B+B+树索引树索引） n n 散散列索引。索引基于将值平均分布到若干散列列索引。索引基于将值平均分布到若干散列 桶中。桶中。 /794 索引简介索引简介 n n 索引是加速查询操作的辅助文件结构索引是加速查询操作
4、的辅助文件结构 n n 包括树型索引和包括树型索引和HashHash索引索引 n n 一个索引可认为是一个一个索引可认为是一个data data entryentry的集合，通的集合，通 过它可快速地找到相应的记录所在的位置过它可快速地找到相应的记录所在的位置 n n 需要考虑的两个问题需要考虑的两个问题 n为了方便查询如何组织data entry ndata entry的构成 /795 索引的例子索引的例子 Smith,44,3000 Jones,40,6003 Tracy,44,5004 Ashby,25,3000 Basu,33,4003 Bristow,29,2007 Cass,50,
5、5004 Daniels,22,6003 age h1 H(age)=00 H(age)=01 H(age)=10 3000 3000 5004 sal h2 H(sal)=00 H(sal)=11 5004 4003 2007 6003 6003 File hashed on age File of pairs hashed on sal /796 聚集聚集索引索引 vs vs 非非聚集索引聚集索引 n n 如果文件中记录的次序同索引中如果文件中记录的次序同索引中data data entryentry的的 次序是相同的，则这个索引是次序是相同的，则这个索引是Clustered(Cluste
6、red(聚簇聚簇 的的) ) n n 一个表只有一个一个表只有一个ClusteredClustered索引，但有多个索引，但有多个 unclusteredunclustered索引索引 n n 鉴于高昂的维护代价，即使是一个鉴于高昂的维护代价，即使是一个 ClusteredClustered 索引也经常是不严格排序的索引也经常是不严格排序的 n用溢出链表的形式 n定期重新排序 nupdate操作与Clustered n n 对对RangeRange查询查询ClusterClustereded的作用比较大的作用比较大 /797 聚集聚集索引索引 . . Index entry Data entr
7、y Data Records Index file Data file /798 非非聚集索引聚集索引 . . Index entry Data entry Data Records Index file Data file /799 稠密索引稠密索引 vs vs 稀疏索引稀疏索引 n n 如果表在该属性上出现的所有值在索引文件中如果表在该属性上出现的所有值在索引文件中 均至少有一个均至少有一个data data entryentry与之相对应则为与之相对应则为densdense e 索引。索引。 /7910 Dense Index Files (Cont.)Dense Index Files
8、 (Cont.) n n Dense Dense index index on on dept_namedept_name, , with with instructor instructor file file sorted sorted on on dept_namedept_name /7911 Sparse Index FilesSparse Index Files n n Sparse Sparse IndexIndex: : contains contains index index records records for for only only some some searc
9、h-key values.search-key values. nApplicable when records are sequentially ordered on search-key n n To locate a record with search-key value To locate a record with search-key value K K we: we: nFind index record with largest search-key value nr/fr， 其中其中nrnr表示将要存储的记录总数，表示将要存储的记录总数，frfr表示一个桶中能表示一个桶中能
10、 存放的记录数目。当然，这种表示是以在选择散列函存放的记录数目。当然，这种表示是以在选择散列函 数的记录总数已知为前提的。数的记录总数已知为前提的。 n n 偏斜偏斜 某些桶分配到的记录比其他桶多，所以即使某些桶分配到的记录比其他桶多，所以即使 其他桶仍有空间，某个桶仍可能溢出。这种情况称为其他桶仍有空间，某个桶仍可能溢出。这种情况称为 桶偏斜桶偏斜 。偏斜发生的情况有两个：。偏斜发生的情况有两个： 1. 1. 多个记录可能具有相同的搜索码。多个记录可能具有相同的搜索码。 2. 2. 所选的散列函数可能会造成搜索码的分布不均所选的散列函数可能会造成搜索码的分布不均 /7942 桶的溢出处理桶的
11、溢出处理 n n 桶的数目选择桶的数目选择 (nr/fr) (nr/fr) (1+d),(1+d),其中其中d d是避让因子是避让因子, , 其典型值约为其典型值约为0.20.2 n n 溢出桶溢出桶 尽管分配的桶比所需的桶多了一些尽管分配的桶比所需的桶多了一些, ,桶溢出桶溢出 还可能发生。我们用溢出桶来处理桶溢出问题。如果还可能发生。我们用溢出桶来处理桶溢出问题。如果 一条记录必须插入一条记录必须插入b b，而桶，而桶b b已满，系统会为桶已满，系统会为桶b b提供提供 一个溢出桶，并将此记录插入到这个溢出桶中。如果一个溢出桶，并将此记录插入到这个溢出桶中。如果 溢出桶满了，系统会提供另一
12、个溢出桶，如此继续下溢出桶满了，系统会提供另一个溢出桶，如此继续下 去。一个给定桶的所有溢出桶用一个链接列表链接在去。一个给定桶的所有溢出桶用一个链接列表链接在 一起，使用这种链接列表的溢出处理称为溢出链。一起，使用这种链接列表的溢出处理称为溢出链。 n n 开散列 开散列 上面描述的这种散列结构称为闭散列，另一上面描述的这种散列结构称为闭散列，另一 种方法称为开散列，它的桶集合是固定的，没有溢出种方法称为开散列，它的桶集合是固定的，没有溢出 链。它与闭散列不同，当一个桶满了以后，系统将记链。它与闭散列不同，当一个桶满了以后，系统将记 录插入到初始桶集合的其他桶中。一种方法是使用录插入到初始桶
13、集合的其他桶中。一种方法是使用 下一个有空间的桶，这个方法称为线性探索法。下一个有空间的桶，这个方法称为线性探索法。 /7943 散列索引散列索引 散列索引散列索引 散列不仅可以用于文件的组织散列不仅可以用于文件的组织, ,还可以用于索引结构的创建。散列索引还可以用于索引结构的创建。散列索引 将搜索码及其相应的指针组织成散列文件结构。我们将散列函数作用于搜索码以将搜索码及其相应的指针组织成散列文件结构。我们将散列函数作用于搜索码以 确定对应的桶，然后将此搜索码及相应的指针存入此桶（或溢出桶）中。确定对应的桶，然后将此搜索码及相应的指针存入此桶（或溢出桶）中。 ( (如下图所示）如下图所示） 桶
14、桶1 1 A-215A-215 A-305A-305 A-217A-217 A-102A-102 A-101A-101 A-110A-110 A-218A-218 A-201A-201 桶桶2 2 桶桶3 3 桶桶4 4 A-217A-217BrightonBrighton750750 A-101A-101DowntownDowntown500500 A-110A-110DowntownDowntown600600 A-215A-215MianusMianus700700 A-102A-102PerryidgePerryidge400400 A-201A-201PerryidgePerryid
15、ge900900 A-218A-218PerryidgePerryidge700700 A-305A-305Round HillRound Hill350350 桶桶0 0 /7944 X各位相加 mod 7 Deficiencies of Static HashingDeficiencies of Static Hashing n n In In static static hashing, hashing, function function h h maps maps search-key search-key values values to to a a fixed fixed se
16、t set of of B B of of bucket bucket addresses. addresses. Databases Databases grow grow or or shrink shrink with with time. time. nIf initial number of buckets is too small, and file grows, performance will degrade due to too much overflows. nIf space is allocated for anticipated growth, a significant amount of space will be wasted initially (and buckets will be underfull). nIf database shrinks, again space will be wasted. n n One One solution: solution: periodic periodic re-org
