索引的概念、数据结构、原理等

索引是啥

数据库索引可以类比为一本书的目录，主要的目的就是快速的定位到目标。这需要支持快速搜索的数据结构的支持，比如哈希表、有序数组和搜索树。

索引的几种形态

根据底层数据结构的不同，大致有三种类型的索引结构

1）基于哈希表的索引
适用于等值查询的场景
缺点：对区间查找不友好

2）有序数组：
优点：利用二分查找，等值查询和范围查询性能都很好
缺点：对动态插入、删除、更新不友好
适用于静态数据或变动不频繁的场景

3）搜索树
目前大部分数据库引擎都用的该方案，这里引出几个问题

为什么不用二叉搜索树？
答：因为二叉树的高度很高，而索引会存放在磁盘上，这将导致数据查询过程需要多次访问磁盘，这会大幅降低搜索效率，所以使用多(1000+)叉树

B树和B+树的区别？
答：
B+树和B树相比，主要的不同点在以下3项：

内部节点中，关键字的个数与其子树的个数相同，不像B树，子树的个数总比关键字个数多1个
所有指向文件的关键字及其指针都在叶子节点中，不像B树，有的指向文件的关键字是在内部节点中。换句话说，B+树中，内部节点仅仅起到索引的作用，真正的数据都存储在叶子节点
在搜索过程中，如果查询和内部节点的关键字一致，那么搜索过程不停止，而是继续向下搜索这个分支，直到叶子节点

根据B+树的结构，我们可以发现B+树相比于B树，在文件系统，数据库系统当中，更有优势，原因如下：

B+树的磁盘读写代价更低
- B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。
B+树的查询效率更加稳定
- 由于内部结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
B+树更有利于对数据库的扫描
- B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的range query，B+树有着更高的性能。

索引数据结构

InnoDB与MyISAM

MyISAM使用的是B+Tree，叶节点存放的数据是记录的地址，即一份映射关系。主键索引树和非主键索引树结构上没区别

InnoDB使用的也是B+Tree，和MyISAM相比最大的区别是他的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是分离的。非主键树叶子节点存放的是主键的值，而主键树叶子节点存放的是整条记录。因此InnoDB要求表必须要有主键，如果未配置那么会默认生成一个主键。同样的如果重建主键索引（先drop再add），相当于整个表都要重建（包括其他非聚合索引树）

延伸：
两种引擎最大的区别就是InnoDB支持事务处理、外键和行级锁；MyISAM强调的是性能，更多适用读的场景。

页分裂与优化

B+树索引的维护
- 新插入数据，要在主键树节点（存放在Page中：类似数组）中插入
  - 插入尾部无影响（追加操作；自增主键就是这样做的）
  - 插入中间需要移位
- 如果Page满了，还需要进行页分裂，要申请一个新的数据页并移动数据，性能很差
  - 页分裂
    - 分裂后，两个page数据各占50%
    - 会导致空间利用率下降，优点是适合于随机插入的场景
    - 目前InnoDB的优化策略（0%分裂策略）
      - 页满了之后，申请新的空间并不移动老数据
      - 针对递增递减场景很合适，如果随机插入反而不如50%策略
  - InnoDB为每个索引页维护了一个上次插入的位置，以及上次的单调情况
    - 根据这些信息判断插入到页面的记录是否满足单调条件，如果满足那么执行0%分裂，否则执行50%分裂
    - 这样会有bug，3,4,5,6在一个块且递增，接下来插入9->8->7都会执行0%策略导致页利用率极低
    - 优化策略，分裂时采用『1策略』，至少带着最后一位一起分裂
- 因删除操作而导致的页合并
- 为什么经常要求table有一个自增主键？
  - 如果是业务主键无法保证有序递增，这可能会导致移位（50%分裂）降低空间利用率
  - 在其他非主键索引构成的树中，叶子存放的是主键，所以使用自增主键占用的空间更小
  - 主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间就越小

联合索引的原理

key ‘Index_Uni’ (‘name’,’age’) 假设根据name和age两个字段建立了联合索引，那么这颗树叶子节点应该是这样的
(‘luyu’,10) (‘luyu’,11) (‘luyu’,12) (‘mike’,10) (‘mike’,12) …
当我们执行如下查询

1	select * from table where name = 'luyu' and age = 12;

此时第一步会根据二分查找定位到’luyu’
Ps这里有个猜测，因为找到’luyu’之后如果要找age=12的记录采用遍历的话时间复杂度较高，所以找到’luyu’应该是第一个和最后一个，然后再根据age在[10,12]这里进行二分查找

联合索引实例

只有待查询的数据在当前范围内有序才能使用索引

a/b/c联合索引：
select a from table where a = 10 and b <= 20 and c > 20
a b会生效
select a from table where a < 10 and b <= 20 and c > 20
a会生效

name/age联合索引：
select * from table1 where name like ‘张%’ and age = 12;
只有name会生效

为什么会有最左匹配

看了联合索引树叶子节点的排列形式应该就清楚为什么要最左匹配了
因为如果最左都不匹配根本无法获取当前列的有序数据，更别提使用算法去查找了

索引覆盖

为了避免回表（额外访问1次主键树）
比如 select Id from t where k = 1 此时Id已经存在叶子节点了无需回表

select v from t where k = 1 如果存在 k v的联合索引，此时也无需回表查询
这也是常见的一种优化手段

索引下推

key ‘Index_Uni’ (‘name’,’age’)
select * from tuser where name like ‘张%’ and age=10;
此时只有name的索引会生效，MySQL5.6之后采用了优化策略，在定位到’张%’后，无需立即回表查询对应age=10的记录，而是可以先在索引树上遍历age=10的记录再回表查询。

数据库索引的查询算法

t1(a int primary key, b int key)

1	select * from t1 where b >= 4;

上面sql等价于查找第一个b=4的位置

1	select * from t1 where b <= 4;

上面sql等价于查找最后一个b=4的位置

后续会单独写一篇二分查找的文章解决类似的问题

一条SQL语句慢的原因

偶尔慢

1.数据库在刷页，redo log和内存中的事务刷到磁盘中
2.拿不到锁，block住

日常慢

1.没有索引
2.有索引但是没用到
2.1 索引field函数操作/不符合最左匹配
2.2 数据库选错索引
有时候即使一个字段上有索引也不会走，数据库会判断走索引和全表扫描的优劣，判断是通过采样来决定的（这意味着有可能判断错误），此时可以使用force index(xx)