数据结构

B+树

结构

插入节点

删除节点

索引原理

logn

索引的数据结构是B+树，而树的查找效率是logn，要比顺序查找的效率n快的多，因此在通过主键（聚集索引）查询数据时，效率是最快的。对于非主键的条件查询，使用辅助索引帮助优化查询效率。

顺序IO

由于索引只包含索引列信息，不包含数据信息，因此索引树大小是较小的，在现代计算机硬件条件下，基本所有索引都是可以全部加载在内存中的，因此可以近似看作在查找索引首地址时是一次随机IO操作，之后将所有索引信息读取到内存中是多次顺序IO操作。

索引的查找操作是在内存中进行的，速度很快。

随机IO

如果要查询的列不全部在辅助索引中，则在匹配到索引列后，要根据索引列记录的主键再通过聚集索引进行一次查找，这种操作叫做回表，回表操作是随机IO操作，是索引的性能瓶颈。

因此，这里可以总结一下索引的作用：

  1. 索引拥有logn的匹配速度
  2. 索引的加载可以看作是一次随机IO+多次顺序IO
  3. 索引的匹配是在内存中进行的
  4. 根据索引确定数据地址后只需要IO很少一部分数据

设计规范

设计原则

  1. 尽可能的减少回表操作。
  2. 尽可能的减少要扫描的记录数。
  3. 尽可能的避免额外的排序。

三星索引

  1. 第三星
    对于要查询的所有字段，全都添加到索引中，这里不考虑顺序。
    索引中包含全部的要查询内容，可以完全避免回表查询，将过滤掉绝大部分的随机读访问，对性能的提升很明显。但会导致索引的增大，极端情况与表记录完全一致
  2. 第一星
    根据where中谓词，最小化要扫描的索引片。将范围查询的索引字段放在索引的后面，等值的放在前面。要扫描的索引记录少即代表了可能回表的次数的减少
  3. 第二星
    利用索引的有序性避免排序。对于where a = 1 and b = 1 order by c的语句，索引(a,b,c)中对于a = 1 and b = 1的记录已经是按照c进行排序了，因此这时查询可以不需要再进行额外的排序直接返回。

由于目前排序的成本越来越低，在索引设计时，优先满足第三星，第一星为准。

注意事项

  1. 索引包含的列不要过多，极端情况下包含所有的列信息，造成巨大的索引表，会极大的影响性能。
  2. 索引字段不要太长，索引越长，占空间越大，内存中能容纳的索引数量越少，每个内存页加载的索引数量页越少，查找性能越低。
  3. 根据索引回表必定存在随机IO，在数据小的情况下反而不如全表顺序扫描
  4. 索引数量不要太多，数据的修改需要同步维护索引，带来额外的维护成本。要遵循二八原则，只对真正需要索引优化的地方使用索引。