数据库索引
基本概念
数据库索引是以额外的写操作和存储空间为代价来提升数据库查找性能的一种数据结构.
索引是用来快速定位数据表中的数据，使用索引能够避免查找数据表时遍历所有数据．可以使用数据表的一列或多列来创建索引，可以提供快速随机查找和高效访问有序记录的基础．
索引是数据表中选中的列的副本，可以非常有效的进行搜索，其中包括低级磁盘块地址或者直接到源数据的链接．
索引类型
有两种基本的索引类型
- 顺序索引
基于值的顺序排序 - 散列索引
基于将值平均分布到若干散列桶中．一个值所属的散列桶是由一个函数决定的．
顺序索引
为了快速随机访问文件中的记录，可以使用索引结构，每个索引结构与一个特定的搜索码相关联，这个搜索码可以快速对应到相应的记录．
顺序索引按顺序存储搜索码的值，并将每个搜索码与包含该搜索码的记录关联起来．
一个文件可以有多个索引，分别基于不同的搜索码，基于其在磁盘上的排布可以分为以下两类
- 聚焦索引(clustering index)
如果包含记录的文件按某个搜索码指定的顺序排序，那么该搜索码对应的索引称为聚焦索引(clustering index), 聚焦索引也成为主索引. - 辅助索引(secondary index)
搜索码指定的顺序与文件中记录的物理顺序不同的索引称为非聚焦索引(nonclustering index) 或 辅助索引(scondary index)
稠密索引和聚焦索引
索引项(index entry)或索引记录(index record)由一个搜索码值和指向具有该搜索码值的一条或多条记录的指针构成．指向记录的指针包括磁盘块的标志和标识磁盘块内记录的块内偏移量
我们可以使用的顺序索引有两类
- 稠密索引(dense index)
在稠密索引中，文件中的每个搜索码值都有一个索引项．
在稠密聚焦索引中，索引项包括搜索码值以及指向具有该搜索码值的第一条数据记录的指针具有相同搜索码值的其余记录顺序的存储在第一条数据记录之后．
在稠密非聚集索引中，索引必须存储指向所有具有相同搜索码值的记录的指针列表． - 稀疏索引(sparse index)
在稀疏索引中，只为搜索码的某些值建立索引项.
只有当索引是聚集索引时才能使用稀疏索引．为了定位一条记录，我们找到其最大搜索码值小于或等于所查找记录的搜索码值的索引项．然后从该索引项指向的记录开始，沿着文件中的指针查找，直到找到所需记录为止.
多级索引
当数据表非常大时，该表所创建的索引也会很大，因此，我们像对待其他任何顺序文件那样对待索引文件，并且在原始的内层索引上构造一个稀疏的外层索引，因为索引总是有序的，所以外层索引可以是稀疏的．之后可以在外层索引上使用二分法搜索对应的记录.
索引的更新
无论采用何种形式的索引，每当数据表中有记录插入，删除或更新时，索引都需要更新，这就是索引带来的额外的写操作．
更新操作可以理解为对旧记录的删除和新纪录的插入，因此，只需要考虑索引的插入和删除
插入
系统首先用出现在待插入记录的搜索码值进行查找，并根据索引是稠密索引还是稀疏索引进行下一个操作
- 稠密索引
- 如果该搜索码值不在索引中，系统就在索引中合适的位置插入具有该搜素码值的索引项
- 否则做如下操作
- 如果索引项存储的是指向具有相同搜索码值的所有记录的指针，系统就在索引想中增加一个指向新纪录的指针
- 否则，索引项存储一个仅指向具有相同搜索码值的第一条记录的指针，系统把待插入的记录放到具有相同搜索码值的其他记录之后
- 稀疏索引
假设索引为每个块保存一个索引项．如果系统创建一个新的块，它会将新块中出现的第一个搜索码值插入到索引中．如果新插入的记录中含有块中最小搜索码值，那么系统就更新指向该块的索引项，否则，系统对索引不做任何改动
删除
为删除一条记录，系统首先查找要删除的记录，下一步操作取决于索引是稠密索引还是稀疏索引
- 稠密索引
- 如果被删除的记录是具有这个特定搜索码值的唯一的一条记录，系统就从索引中删除相应的索引项
- 否则做如下操作
- 如果索引项存储的是指向所有具有相同搜索码值的记录的指针，系统就从索引项中删除指向被删除记录的指针
- 否则索引项存储的是指向具有该搜索码值的第一条记录的指针．这是，如果被删除记录是具有该搜索码的第一条记录，系统就更新索引项，使其指向下一条记录
- 稀疏索引
- 如果索引不包含具有被删除记录搜索码值的索引项，则索引不做任何修改
- 否则做如下操作
- 如果被删除的记录是具有该搜索码值的唯一记录，系统用下一个搜索码值的索引记录替换相应的索引记录．如果下一个搜索码值已经有一个索引项，则删除该索引项
- 否则，如果该搜索码的索引记录指向被删除的记录，系统就更新索引项，使其指向具有相同搜索码值的下一条记录
辅助索引
辅助索引必须是稠密索引，对每个搜索码值都有一个索引项，而且对文件中的每条记录都有一个指针.
索引的实现
顺序索引的实现常使用 B+ 树实现，对于 B+ 树不再赘述