索引与散列

it2022-06-27  90

许多查询只涉及文件中的少量记录,如查询ID为22201的学生的总分数,如果系统读取每一个元组并检查,这样的操作方式是低效的。理想情况下,需要系统能够直接定位记录,为了支持这样的访问方式,我们设计了与文件相关的数据结构-索引。

基本概念

有两种基本的索引类型

顺序索引(Ordered Indices):基于值的顺序排序。哈希索引(Hash Indices):基于值在一系列桶中的均匀分布,值属于哪个散列桶由哈希函数决定。

对于不同的索引技术,必须基于以下几种因素:

访问类型(Access types):能有效支持的访问类型,包括访问具有特定属性或者属性值落在某个范围的记录。访问时间(Access time):查询中访问数据项或项集所需要的时间。插入时间(Insert time):插入新数据项的时间,包括找到正确的位置插入数据项和更新索引所需要的时间。删除时间(Delete time):删除数据项的时间,包括找到要被删除的项和更新索引所需要的时间。空间开销(Space overhead):索引结构所占据的额外空间。

我们将用于查找记录的属性或属性集称为搜索码(search key)

顺序索引

聚集索引(clustering index):记录在文件中的物理顺序与搜索码的顺序一致,也称为主索引(primary index),聚集索引的搜索码常常是主码,但并非总是如此。

非聚集索引(nonclustering index)或辅助索引(secondary index):搜索码的顺序与文件记录的顺序不同。

一般而言,一个表中只有一个聚集索引。

稠密索引和稀疏索引

索引项(index entry)由一个搜索码和指向该搜索码的一条或多条指针构成。

稠密索引(dense index):每个搜索码值都有一个索引项。稀疏索引(sprase index):只为某些搜索码具有索引项,只有当关系按照搜索码一致的顺序排列时才能使用稀疏索引,换句话说,只有索引是聚集索引才能使用稀疏索引,为了定位一条记录,我们找到小于等于搜索码值的最大的索引项,然后从该索引项开始顺序往下查找。

 

 

如图,在稠密索引中查找22222可直接通过索引项的指针找到,在稀疏索引中,需要先找到10101,然后根据其索引项的指针顺序往下查找。

稠密索引通常比稀疏索引查找的更快,但稀疏索引所占空间小,插入删除的开销也小。

折中:对于每个块可以建立一个稀疏索引,数据库的查询时间主要由块从磁盘到内存的时间决定,块在内存中查找时间与之相比是可以忽略的。

多级索引

对于10000个块(假定一个块4KB)的索引,如果采用二分法,需要读取14次,读一块平均耗时10ms,该搜索将耗时140ms,意味着每秒中只能进行7次索引搜索。

为了处理这个问题,在原始的索引上加了一个外层的稀疏索引。

10000个内层索引块需要10000个外层索引项,也就是100块,假设外层索引已经在内存中,则一次查询只需要读一个索引块,不需要使用二分法,因此每秒钟可以执行14次索引查找。如果二级索引仍然很大,可以再加一层成为三级索引,以此类推。

索引的更新

单级索引的更新

插入 稠密索引 不在索引中就插入合适的位置。在索引中,如果索引项存储的是同一搜索码所有记录的指针,则系统增加一个指向新纪录的指针,否则,索引项仅存储第一条记录的指针,将带插入的记录放在其他记录之后。稀疏索引 将新块的第一个搜索码值插入到索引中,如果新插入的块中有最小搜索码值,系统更新指向该块的索引,否则,不做任何改动。删除 稠密索引 如果删除的是该搜索码的唯一一条记录,系统从索引中删除对应的索引项。如果索引项存储的是指向所有具有搜索码的指针,则从索引项中删除指向被删除记录的指针。如果索引项存储的是指向该搜索码的第一条记录的指针,如果被删除的是第一条记录的指针,则更新索引项,使其指向下一条。稀疏索引 如果不包含该搜索码的索引项,则不修改索引。否则,如果是唯一一条记录,则用下一个搜索码值替换该索引项,如果下一个有索引项,则直接删除。如果不是唯一记录,则索引项更新为相同搜索码值的下一条记录。

转载于:https://www.cnblogs.com/qbits/p/10713449.html


最新回复(0)