3 线性索引查找

Wu Jun 2019-05-23 19:48:22
01 数据结构与算法 > 数据结构 > 03 查找

1 稠密索引

稠密索引:在线性索引中,将数据集中的每个记录对应一个索引项,索引项按照关键码有序排列。

但数据量大时,可能由于内存有限,需要反复访问磁盘,降低性能。

2 分块索引(分块查找)

分块索引:对数据集进行分块,使其块间有序,块内无序。对每一块建立一个索引项。

分块索引的索引项结构分三个数据项:

在分块索引表中查找,就是分两步进行:

  1. 在分块索引表中查找要查关键字所在的块。
  2. 根据块首指针找到相应的块,并在块中顺序查找关键码。

增加了整体查找的速度,普遍被用于数据库表查找等技术的应用当中。

3 倒排索引

倒排索引:不是由记录来确定属性值,而是由属性值来确定记录的位置。

索引项包括一个属性值和具有该属性值的各记录的地址。