索引
索引的作用
引入索引是为了 加快数据的访问，就像查字典一样，我们根据拼音或者偏旁查找具体的字会更快
索引项
- 搜索键：用于查找记录的属性或属性集合
- 指针：指向与搜索键值匹配的一个或多个记录
索引文件
索引文件是由一系列 索引项 组成的，索引文件通常比数据文件小
索引的基本类型
- 有序索引：搜索键按顺序存储
- 哈希索引：用哈希函数将搜索键分布到不同的桶中
索引评估指标
- 支持的访问类型
- 指定某属性值的记录，例如查找
age=20的人 - 范围查询，即属性值在某范围内的记录，例如查找
10 <= age <= 20的人
- 指定某属性值的记录，例如查找
- 访问时间
- 插入时间
- 删除时间
- 空间开销
有序索引
有序索引就是指，索引项要根据搜索键的值排序
主索引 (聚集索引)
主索引是与文件的顺序结构紧密相关的索引，它的搜索键决定了文件记录的顺序，通常在 顺序文件 中使用
顺序文件就是指，文件记录已经按照某个规则(比如某个属性的值)进行排序过了
主索引通常是主键，但并不绝对
辅助索引 (非聚集索引)
辅助索引为非主键字段提供索引支持，它的搜索键与文件的顺序无关
顺序索引文件
索引顺序文件是一种特殊的顺序文件，它结合了顺序文件的优势和索引的优势。它使用了一个主索引来对记录进行排序
数据记录通过主索引的查询指针快速访问，而无需扫描整个文件
密集索引和稠密索引
密集索引
每个搜索键值都有一个索引记录，简单来说，就是每条记录的搜索键值都必须有一个对应的索引项（可以是多对一，即多条记录有相同的索引键值）
密集聚集索引
存储每个搜索键值的索引记录，并指向该值的第一个记录，后续记录按顺序存储
也就是相同的搜索键就只有一个索引项，该索引项的指针指向第一个记录，后续的记录按顺序存储
密集非聚集索引
存储相同搜索键值的所有记录的指针
相同的搜索键只有一个索引项，每个索引项的指针指向一个 桶，这个桶里存储了对应搜索键的所有记录的指针
稠密索引
只为某些搜索键值存储索引条目，适用于按搜索键顺序排列的记录
有些记录的搜索键值没有对应的索引项，索引项中，每个搜索键就是一组记录的开头，就相当于对记录进行分组，然后每个组中开头的记录的搜索键值作为索引项，所以要求要按顺序排列
稀疏索引相比于密集索引占用更少的空间和维护开销，但查找记录时可能较慢
优化：在每个 数据块 中放一个索引条目，指向该块中最小的搜索键值
多级索引
如果主索引太大而无法放入内存，可以将其作为顺序文件，再对其构建稀疏索引
- 外层索引：指向主索引的稀疏索引
- 内层索引：实际的主索引文件
如果外层索引还是太大，可以在构建一层索引
多级索引插入或者删除记录时，要同时更新每一层的索引，所以层级越多，相应的开销也越大
索引更新
多级索引，插入和删除的算法只是单级索引的简单扩展。也就是说，多级索引的插入和删除操作遵循相同的基本规则，只是它们会作用于多个索引层次
单级索引删除：
-
稠密索引：
- 删除对应记录，如果搜索键值只有这么一个对应的记录，那么这个搜索键的索引项也要删除
-
稀疏索引：
- 如果删除的记录的搜索键在索引文件中，那么删除该记录后，它对应的索引项也要删除，然后使用这条记录的下一条记录的搜索键替换
- 如果下一个记录的搜索键值已经在索引中有对应的条目，那么就直接删除，不用替换
单级索引插入:
-
稠密索引：
- 如果插入记录的搜索键在索引中不存在，就插入这个搜索键到索引中
-
稀疏索引：
- 如果索引是稀疏的，并且每个索引条目代表的是文件中的一个块，那么只有在新插入的记录导致了新块的创建时，才需要修改索引。
- 如果新块创建了新的记录，新块中的第一个搜索键值会被插入到索引中
位图索引
-
Bitmap 索引本质上是一个 位图
-
对于关系中的 每一条记录，都有一个对应的位
-
每个属性的每个可能值都有一个独立的位图。位图的长度等于关系中记录的数量，每一位代表一条记录
如上图所示，我们有一张表，具有5条记录，然后我们为 性别和收入水平 这两个字段创建了位图索引
比如说，下面这个，就是 字段性别的一个取值（男）的位图，10010表示第1条和第4条记录是男 (第1位和第4位是1)
然后我们可以对不同的位图进行与操作等等，从而实现查询，比如 m和L1这两个位图相与，只有第1位为1，也就表示，性别为男，收入水平为L1的记录只有第一条
B树索引
B树
B树是一种多路平衡查找树
- 平衡：所有的叶节点都在同一层
- 有序：节点内有序，任意节点的左子树都小于它，右子树都大于它
- 多路：对于 m 阶B树
- 最多：m个分支，m-1个元素
- 最少：
- 根节点：2个分支，1个元素
- 其他节点：[m/2]个分支，[m/2]-1个元素
B树是向上生长的，也就是说，当某个节点溢出时，它分进行分裂，分裂成一颗子树，这颗子树的根节点合并到之前的父节点，是一个逐渐往上生长的过程
B树的节点结构
- K 表示搜索键
- P 表示指向子节点指针
- B 表示指向记录的指针
非叶子节点
叶子节点
整体结构如下：每个节点的元素都能直接指向记录
B+树索引
B+树
B+树的大致结构和B树相同，以下介绍不同的点：
- 对于B树来说，节点的元素个数总是比分支数少1，但是对于B+树来说，节点的元素个数总是和分支树相等
- B+树的叶子节点通过一个链表串联起来
B+树的节点结构
对于叶子节点来说，P表示的是指向记录的指针，对于非叶子节点来说，P表示的是指向子节点的指针
其中叶子节点这一层通过链表串联起来
整体结构如下：只有子节点的元素能够直接指向记录
B树和B+树索引的对比
- B树的每个节点的元素都能直接指向记录，B+树只有子节点的元素能够直接指向记录，B+树的子节点是记录的索引，内部节点是索引(子节点)的索引，所以B+树是一个多级索引
- B树的搜索键只出现一次，不会重复出现，B+树的搜索键会重复出现，父节点的搜索键也会出现在对应子树的子节点中，从而使得B+树的子节点包含所有的搜索键（这也说明了为什么B+树节点的元素个数总是和分支数相等）
- B树能够以更小的空间开销建立索引，每个节点都包含数据，遍历不方便，适合较小范围记录查询，不适合范围查询；B+树会造成重复搜索键的开销，但只有子节点包含数据，且通过链表串联，适合范围查询
- B树的节点更新更加复杂，因为所有节点都包含数据，B+树的更新会简单点，内部节点只包含索引，子节点包含数据
总结
-
B树：适合单记录查询，尤其是对于查找操作要求较高的场景，且数据较为简单。B树在范围查询时的性能较差，且由于 数据存储在每个节点中，可能会导致空间利用率低
-
B+树：由于叶子节点的链表结构，特别适合范围查询和顺序扫描，空间利用率较高。它的 多级索引结构 使得它在处理大规模数据集时，尤其是数据库的索引查询中，具有显著优势