基本概念

[1] 索引（Index）是帮助数据库高效获取数据的数据结构

[2] 索引分为顺序索引和散列索引, 顺序索引基于值的顺序排序

聚集索引和辅助索引

稠密索引和稀疏索引

[1] 稠密索引为每个搜索码值建立索引, 稀疏索引只对某些搜索码值包含索引项

[2] 只有索引是聚集索引时才能使用稀疏索引

[3] 为每个块建立一个索引是较好的存取时间和空间开销的折中

多码访问

[1] 具有两级和两级以上的索引称为多级索引

[2] 包含多个属性的搜索码称为复合搜索码, 搜索码值按照字典序排序
使用多个单码索引的缺点: 为了得到一个很小的结果集, 必须扫描大量指针
解决: 位图索引 / R树(地理数据类型)

最左匹配原则
[1] 针对：联合索引

[2] 最左匹配原则遇上范围查询就会停止, 剩下的字段都无法使用索引。
例如a = 1 and b = 2 a、b字段都可以使用索引, 因为在a值确定的情况下b是相对有序的；
而a > 1 and b = 2, a字段可以匹配上索引, 但b值不可以, 因为a的值是一个范围。

[3] b = 2 如果建立(a, b)顺序的索引, 匹配不到(a, b)索引；
但是如果查询条件是a = 1 and b = 2或者a = 1(又或者是b = 2 and a = 1)就可以, 因为优化器会自动调整a, b的顺序。
再比如a = 1 and b = 2 and c > 3 and d = 4如果建立(a,b,c,d)顺序的索引, d是用不到索引的, 因为c字段是一个范围查询, 它之后的字段会停止匹配。

[3] 覆盖索引: 在创建多列索引的时候, 要查询出的列和索引是对应的, 不做回表操作
存储一些不是搜索码属性的属性值以及指向记录的指针
优点: 仅仅使用索引就可以回答一些查询, 减小搜索码的大小, 使非叶结点有更大的扇出, 从而降低索引高度

索引技术的评价

[1] 访问类型、访问时间、插入时间、删除时间、空间开销

[2] MySQL数据库支持多种索引类型, 如BTree索引, 哈希索引, 全文索引等等。

[3] KV存储引擎的索引根据key是否有序, 分为两种：
如果key无序, 则可以采用hash的方法
如果key有序, 则可以采用B+树的方法, 或者类B+树的方法。

索引的更新

插入

[1] 稠密索引:
用出现在待插入记录中的搜索码进行查找, 如果不在索引中就在合适的位置插入索引项; 否则:

• 如果索引项存储的是指向具有相同搜索码所有记录的指针, 就在索引项中增加一个指向新记录的指针;
• 否则索引项存储的是指向具有相同搜索码的第一条记录的指针, 把待插入的记录放到具有相同搜索码的其他记录之后

[2] 稀疏索引: 如果系统创建一个新的块, 将新块中出现的第一个搜索码插入到索引中; 如果这条新插入的记录含有块中最小搜索码, 那么系统更新指向该块的索引项, 否则不做任何改动

删除

[1] 稠密索引: 首先查找要删除的记录, 如果是具有这个搜索码的唯一记录, 就删除相应索引项, 否则:

• 如果索引项存储的是指向具有相同搜索码所有记录的指针, 就在索引项中删除指向被删除记录的指针
• 否则索引项存储的是指向具有相同搜索码的第一条记录的指针, 如果被删除的记录是具有该搜索码的第一条记录, 系统更新索引项使其指向下一条记录

[2] 稀疏索引: 如果索引不包含具有被删除记录搜索码的索引项, 索引不必做任何修改; 否则:

• 如果被删除的记录是具有该搜索码值的唯一记录, 系统用下一个搜索码值的索引记录替换相应索引记录; 如果下一个搜索码值已经有一个索引项, 则删除该索引项 (而不是替换)
• 否则如果搜索码的索引记录指向被删除的记录, 就更新索引项使其指向具有相同搜索码的下一条记录

B+树索引

[1] 结构: 平衡树; 多级索引

[2] 叶结点: 所有的搜索码值都出现在某个叶结点中 (使得B+树称为稠密索引)
非叶结点: 形成叶结点的多级稀疏索引, 结点的指针书称为该结点的扇出, 最少n/2，最多n
根结点包含指针数可以小于n/2

[3] 指针Pn将叶结点按搜索码顺序串在一起, 对文件进行高效顺序处理

[4] B+树保证了结点至少半满; 以随机顺序插入, 那么结点在平均情况下会比2/3更满

查询

[1] 步骤

1. 检查当前点, 找到最小的i使得搜索码值Ki大于等于V; 假设找到了这样的值:
   如果Ki等于V, 那么将当前结点置为由Pi+1指向的结点;
   如果Ki大于V, 那么将当前结点置为由Pi指向的结点
2. 如果没有找到这样的Ki值, V大于等于Km-1, 其中Pm为结点中最后一个非空指针。将当前结点置为由Pm指向的结点
   重复以上过程知道访问叶结点
3. 叶结点如果包含等于V的搜索码, 令Ki为第一个这样的值, 则Pi指向具有搜索码Ki的记录
4. 否则失败

[2] 结点大小一般等于磁盘块大小4KB

[3] 与内存中树结构的区别: 结点大, 胖而矮, 读块数少

更新

[1] 插入与分裂

1. 孩子指针的分裂介于原始的和新创建的结点之间
   位于移动到右边结点的指针之间的搜索码值和指针一起移动
   位于留在左边的指针呢之间的搜索码值依然不变
2. 确定插入发生的叶结点l, 如果产生分裂, 则将新结点插入结点l的父结点中

[2] 删除与合并

1. 查找并删除后, 如果结点太小, 递归从父结点中将它删除, 直到树的根结点
2. B+树的非叶结点中的关键码值可能在树的叶结点中并不存在
   参与重新分布的兄弟结点越多, 更新的代价越高

[3] 复杂性: 与B+树高度成正比, 一次插入的I/O次数正比于log(n/2)(N), n为结点中指针的最大值, N为文件中记录条数。实际情况:

• 一次查询一般只需要一次或两次I/O操作: 大部分非叶结点在被访问时已经在数据库缓冲区中
• 一次插入需要更新块的I/O操作仅比一次略多: 叶结点分裂的可能性比较小

不唯一搜索码

[1] 一个关系可以拥有多个包含同一搜索码值的记录
两条或者多条记录在索引属性上拥有相同的值, 那么该搜索码称为不唯一搜索码

[2] 问题: 删除记录的效率
解决方案: 通过创建包含原始搜索码和其他属性的复合搜索码确保搜索码唯一
唯一化属性 / 额外属性: 指向记录的指针(记录号), 或者是拥有相同搜索码值的所有记录中值唯一的其他属性

[3] 不唯一搜索码可以在B+树中只存储一次, 并且为该搜索码值维护一个记录指针的桶
优点: 空间上有效
缺点:

1. 在叶结点保存桶, 需要额外的代码处理可变长的桶;
2. 如果桶存储在单独的块中, 获取记录时可能需要额外的I/O操作;
3. 搜索码值出现次数较多, 记录删除效率不高

B+树索引扩展

B+树文件组织

[1] 索引顺序文件组织缺点: 文件增大时, 索引记录存储在溢出块中, 性能下降

[2] B+树文件组织的叶结点存储记录

• 叶结点存储的记录数目比非叶结点存储的指针数目少 (记录比指针大)
• 树中相邻叶结点可能分布在磁盘中的不同位置, 随着不断进行插入和删除操作, 对叶结点顺序访问需要越来越频繁的等待磁盘寻道——解决: 对索引重建
• 存储大型数据对象: 拆分成小的记录序列并组织成B+树, 按序编号, 或者根据记录在大型对象中字节偏移量进行编号, 编号用作搜索码

[3] 辅助索引和记录重定位

• 即使记录没有更新, B+树文件组织也可能改变记录的位置,
  例如: 分裂后一些记录移动到新的结点, 所有存储了指向重定位过的记录的指针的辅助索引都必须更新
  一个叶结点的分裂可能需要几十甚至几百次I/O操作来更新辅助索引
• 解决方案: 辅助索引不存储指向被索引的记录的指针, 而是存储主索引搜索码属性的值
  例如instructor关系上ID为主索引, dept为辅助索引, 辅助索引中与每个系的名字存放在一起的事相应记录中ID值构成的列表, 而不是指向这些记录的指针
• 查询: 首先用堵住索引找到主索引搜索码的值, 然后用住索引找到对应的记录

B+树索引的批量加载

基于项排序+自底向上构建
[1] 索引的批量加载: 将大量项一次插入到索引中

1. 创建一个含有关系索引项的临时文件
2. 根据构建好的索引的搜索码排序文件, 好处: 所有到特定叶结点的项连续出现, 并且叶结点只需要写出一次
3. 扫描排序好的文件并将项插入到索引中

如果B+树开始为空, 批量加载时结点不需要从磁盘中读取, 即便很多项需要插入到一个结点中, 每一个叶结点只需要一次I/O操作

[2] 从叶子级自底向上构建B+树:

1. 排序好的项分解到块中, 保证每个块中有尽可能多的项, 由此产生的块形成B+树的叶级
2. 每个块中最小值以及指向块的指针用来构建下一级的B+树项, 并且指向块

[3] 建议关系上的索引(除主码上的索引)先删除, 并且插入元组后重新构建索引

B树索引

[1] 在B-Tree中按key检索数据：首先从根结点进行二分查找, 如果找到则返回对应结点的data,
否则对相应区间的指针指向的结点递归进行查找, 直到找到结点或找到null指针, 前者查找成功, 后者查找失败

[2] B树与B+Tree区别:

字符串上的索引和闪存

[1] 字符串上的索引

• 字符串变长: 结点的合并和重新分布取决于结点中空间使用的比例, 而不是结点所能容纳的最大项数
• 字符串很长导致结点扇出降低, 增加树的高度: 使用前缀压缩技术, 只存储搜索码的前缀, 使得这个前缀足以将由该搜索码分开的两棵子树的码值区分开

[2] 闪存

• 通过块组织, B+树索引结构的结点大小比磁盘小得多(因为数据查找快)
• 缺点: 不允许物理层数据就地更新, 每次更新操作转化为整个闪存块的拷贝+写操作, 要求块的旧拷贝随后清除(1ms)