空间存储和索引.ppt

*第四章空间存储和索引续武汉理工大学资源与环境工程学院规划系**空间存储和索引目标和基本思想物理存储介质缓冲区管理存储组织存取路径:索引结构**索引索引:支持对于所要求的数据进行快速定位的附加的数据结构。每个索引结构有一个特定的搜索码与之关联。索引按一定的方式存储搜索码的值,并将搜索码与包含该搜索码的记录关联起来。搜索码:用于在文件中查找记录的属性或属性集。**基本索引结构顺序索引索引基于对搜索码值的一种排序散列索引索引基于将搜索码值平均分布到若干散列桶(hashbuckets)中**基本索引结构:顺序索引顺序索引中按照一定的顺序存储搜索码的值主索引:若文件中的记录按照某个搜索码值的顺序来存储,则这个搜索码所对应的索引称作主索引,或者聚类索引(clusterindex)辅助索引:索引对应的搜索码值的顺序与文件记录的存储顺序不一致,也称作非聚集索引**基本索引结构:散列索引在外存中按照桶散列,通过散列函数将搜索码值对应到桶地址桶(bucket)是能存储一条或多条记录的一个存储单位,每个桶包括一个或多个磁盘块散列牺牲存储效率可以通过可扩充散列,在数据库大小变化时对桶进行分裂或合并,保持一定的空间效率**散列(hashed)索引散列索引,也称为哈希索引。它既是一种查找方法,又是一种存贮方法,称为散列存贮。散列存贮的内存存放形式也称为散列表。散列查找,是通过构造散列函数来得到待查关键字的地址,按理论分析真正不需要用到比较的一种查找方法。例如,要找关键字为k的元素,则只需求出函数值H(k),H(k)为给定的散列函数,代表关键字k在存贮区中的地址,而存贮区为一块连续的内存单元,可用一个一维数组(或链表)来表示。**散列(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(散列表)中,具体表示为:**其中HT就是散列存贮的表,称为散列表。从散列表中查找一个元素相当方便,例如,查找75,只需计算出H(75)=75%13=10,则可以在HT[10]中找到75。544318466075900123456789101112131415HT散列(Hashing)在线性表、树结构中查找记录是通过与关键字的“比较”完成的。顺序查找,比较的结果为“=”或“≠”非顺序查找,比较的结果为“<”,“=”,“>”