空间存储和索引

《空间存储和索引》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2021/7/15第四章空间存储和索引　续武汉理工大学资源与环境工程学院规划系2021/7/152空间存储和索引目标和基本思想物理存储介质缓冲区管理存储组织存取路径：索引结构2021/7/153索引索引：支持对于所要求的数据进行快速定位的附加的数据结构。每个索引结构有一个特定的搜索码与之关联。索引按一定的方式存储搜索码的值，并将搜索码与包含该搜索码的记录关联起来。搜索码：用于在文件中查找记录的属性或属性集。2021/7/154基本索引结构顺序索引索引基于对搜索码值的一种排序散列索引索引基于将搜索码值平均分布到若干

2、散列桶（hashbuckets）中2021/7/155基本索引结构：顺序索引顺序索引中按照一定的顺序存储搜索码的值主索引：若文件中的记录按照某个搜索码值的顺序来存储，则这个搜索码所对应的索引称作主索引，或者聚类索引（clusterindex）辅助索引：索引对应的搜索码值的顺序与文件记录的存储顺序不一致，也称作非聚集索引2021/7/156基本索引结构：散列索引在外存中按照桶散列，通过散列函数将搜索码值对应到桶地址桶（bucket）是能存储一条或多条记录的一个存储单位，每个桶包括一个或多个磁盘块散列牺牲存储效率可以

3、通过可扩充散列，在数据库大小变化时对桶进行分裂或合并，保持一定的空间效率2021/7/157散列(hashed)索引散列索引，也称为哈希索引。它既是一种查找方法，又是一种存贮方法，称为散列存贮。散列存贮的内存存放形式也称为散列表。散列查找，是通过构造散列函数来得到待查关键字的地址，按理论分析真正不需要用到比较的一种查找方法。例如，要找关键字为k的元素，则只需求出函数值H（k），H（k）为给定的散列函数，代表关键字k在存贮区中的地址，而存贮区为一块连续的内存单元，可用一个一维数组(或链表)来表示。2021/7/15

4、8散列(hashed)索引例1，假设有一批关键字序列18,75,60,43,54,90,46，给定散列函数H（k）=k%13，存贮区的内存地址从0到15，则可以得到每个关键字的散列地址为：H（18）=18%13=5H（75）=75%13=10H（60）=60%13=8H（43）=43%13=4H（54）=54%13=2H（90）=90%13=12H（46）=46%13=7于是，根据散列地址，可以将上述7个关键字序列存贮到一个一维数组HT（散列表）中，具体表示为：2021/7/159其中HT就是散列存贮的表，称为散

5、列表。从散列表中查找一个元素相当方便，例如，查找75，只需计算出H（75）=75%13=10，则可以在HT[10]中找到75。544318466075900123456789101112131415HT散列(Hashing)在线性表、树结构中查找记录是通过与关键字的“比较”完成的。顺序查找，比较的结果为“=”或“≠”非顺序查找，比较的结果为“<”，“=”，“>”基本概念散列:由关键字通过确定的对应关系计算得到记录的存储位置的过程称散列。哈希表:按散列形式的记录的集合称散列表或哈希表。所使用的对应关系称散列函数或哈

6、希函数散列查找：也称哈希查找，是由关键字通过计算得到记录存储地址的查找方法。冲突：通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。例：有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k，请画出存储结构图。解：根据散列函数H（k）＝k，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……，对应散列存储表（哈希表）如下：根据存储时用到的散列函数H(k)表达式，即可查到结果！例如，查

7、找key=9,则访问H(9)=9号地址，若内容为9则成功；若查不到，应当设法返回一个特殊值，例如空指针或空记录。地址…9…11…14…232425…39…内容14119232539明显缺点：空间效率低有6个元素的关键码分别为：（14，23，39，9，25，11）。选取关键码与元素位置间的函数为H(k)=kmod7通过哈希函数对6个元素建立哈希表：253923914冲突现象举例：6个元素用7个地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有冲突！0123456所以，哈希方

8、法必须解决以下两个问题：1）构造好的哈希函数（a）所选函数尽可能简单，以便提高转换速度；（b）所选函数对关键码计算出的地址，应在哈希地址内集中并大致均匀分布，以减少空间浪费。2）制定一个好的解决冲突的方案查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。常用的哈希函数