索引底层概念

[dduo518]

索引类型

1. 顺序索引：基于值的顺序

2. 散列索引：基于将值平均分布到若干散列桶中

1.1 顺序索引

1. 聚集索引

包含的记录的文件按照某个搜索码指定的顺序排序

稠密索引

1. 顺序的

2. 每个搜索码都建立索引项

   在稠密非聚集索引中，索引必须存储指向所有具有相同搜索码值的记录的指针列表

   索引的插入

   假设索引为每个块保存一个索引项 如果系统创建一个新的索引块，新块中出现的第一个搜索码值插入到索引中

   如果这条新的插入的记录含有块中的最小搜索码，那么系统就更新指向该块的索引项

   索引的删除

   如果索引不包含具有被删除记录搜索码值的索引项，则索引不必做任何修改

   如果被删除的记录是具有该搜索马志的唯一记录，系统用下一个搜索码值的索引记录替换相应的索引记录，如果下一个搜索码值已经有一个索引项，则删除而不是替换该索引项

   如果该搜索码值的索引记录指向被删除的记录，系统就更新索引项，使其指向具有相同搜索码值的下一条记录

   稀疏索引

3. 顺序的

4. 只为某些值建立索引项

   只有当关系按搜索码的顺序排序存储时才能使用稀疏索引 只有索引时聚集索引时才能使用稀疏索引

   索引的插入

   假设索引为每个块保存一个索引项 如果系统创建一个新的索引块，新块中出现的第一个搜索码值插入到索引中 如果这条新的插入的记录含有块中的最小搜索码，那么系统就更新指向该块的索引项

   索引的删除

   如果索引不包含具有被删除记录搜索码值的索引项，则索引不必做任何修改

   如果被删除的记录是具有该搜索马志的唯一记录，系统用下一个搜索码值的索引记录替换相应的索引记录，如果下一个搜索码值已经有一个索引项，则删除而不是替换该索引项

   如果该搜索码值的索引记录指向被删除的记录，系统就更新索引项，使其指向具有相同搜索码值的下一条记录

   多级索引

   具有俩级或者俩级以上的索引 利用多级索引搜索记录与用二分搜索记录相比需要的IO操作要少的多

   多级索引项对待其他任何顺序文件那样对待索引文件，并且在原始的内层索引上构造一个稀疏的外层索引

   指针指向一个内层索引块

   多码索引

   一个包含多个属性的搜索码 这个索引的结构和任何其他的索引一样，唯一不同的地方时搜索码不是单个属性，而是一个属性列表 在mysql 当我们创建一个复合索引的时候，既创建的为多码索引，索引的码值按照字典顺序排序

在mysql中，如果建立复合索引index(name,age),如果查找的语句为

select name,age from table where name="$name" and age = "$age"

此时复合码上的有序索引可以用来有效的提高查询效率，相比

select * from table where name="$name" and age = "$age"

我们可以不用直接进行二次回表查询得到结果。

2. 非聚集/辅助索引

搜索码指定的顺序与文件中记录的物理顺序不同的索引

辅助索引

辅助索引必须是稠密索引(非聚集)，对每个搜索码值都有一个唯一索引项，而且对文件中的每条记录都有一个指针

候选码上的辅助索引看起来和稠密索引没有太太的区别，只不过索引中一系统的连续值指向的记录不是连续存放的

用一个附加的间接指针层来实现非候选码的搜索码上的辅助索引，在辅助索引中指针并不直接指向文件，而是指向一个包含文件指针的桶

按聚集索引顺序对文件进行顺序扫描时非常有效的，因为文件中记录的物理存储顺序和索引顺序一致，但是，不能时存储文件的物理顺序既和聚集索引的搜索码顺序相同又和辅助索引的搜索码顺序相，由于辅助码的顺序和物理码的顺序不同，因此如果想要按辅助码的顺序对文件进行扫描，那么每读取一条记录都很有可能需要从磁盘读入一个新的块。

辅助索引能够提高使用聚集索引搜索码以外的码的查询性能，但是辅助索引增加了数据库更新的开销

比如 mysql中 用create_at 创建时间建立一个有序索引的时候会建立辅助索引