数据库的索引
磁盘存储器:用来长期联机数据存储的主要介质是磁盘。通常整个数据库都存储在磁盘上。为了能够访问数据,系统必须将数据从磁盘移到主存储器。在完成指定的操作后,修改过的数据必须写回磁盘。
索引:
有两种基本的索引类型:
1. 顺序索引。基于值的顺序排序
2. 散列索引。基于将值平均分布到若干散列桶中。一个值所属的散列桶是由一个函数决定的,该函数称为散列函数。
先来讨论顺序索引,在顺序索引中,有几个重要的概念。
1.
聚集索引(主索引):如果包含记录的文件按照某个搜索码指定的顺序排序,那么该搜索码对应的索引称为聚集索引。
非聚集索引(辅助索引):搜索码指定的顺序与文件中记录的物理顺序不同的索引称为非聚集索引。
2.
稠密索引:在稠密索引中,文件中的每个搜索码值都有一个索引项。
在稠密聚集索引中,索引项包括搜索码值以及指向具有该搜索码值的第一条数据记录的指针。
在稠密非聚集索引中,索引必须存储指向所有具有相同搜索码值的记录的指针列表。
稀疏索引:在稀疏索引中,只为搜索码的某些值建立索引项。
只有索引是聚集索引时才能使用稀疏索引。
3. 多级索引
4. 辅助索引:必须是稠密索引,对每个搜索码值都有一个索引项,而且对文件中的每条记录都有一个指针。
因为索引顺序文件的查询性能随着文件的增大会下降,所以引入了
1. B+树索引:适合于范围查询
2. 散列索引:适合于单个查询
数据库中的索引?
从数据结构角度:
1. B+树索引:适合于范围查询
2. 散列索引:适合于单个查询
3. R树索引:适合于范围查询
4. 全文索引
从物理存储角度:
1. 聚集索引
2. 非聚集索引