【数据库】索引篇

写在前面的话

索引是数据库系统里面最重要的概念之一，也是每一个与数据库相关的开发人员必须要好好掌握的内容，下面是我的理解。

索引模型

索引的出现是为了提高查询效率，但是实现索引的方式却有很多种，一般为这三种模型：哈希表，有序数组，二叉搜索树（也成为二叉排序树）

哈希表

哈希表是键值对的形式（key-value），在数据库中通过查询key,然后进行某种运算得到value(value一般后跟链表的形式显示整行元组），可以看出了如果key不是有序的，那么哈希表的查询是很慢的（需要全部进行遍历）。所以说哈希表这种结构适用于只有等值查询的场景

有序数组

有序数组在等值查询和范围查询场景中的性能就都非常优秀，这个很容易理解啊，二分查找法快速找到位置。
但是吧，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。
所以，有序数组索引只适用于静态存储引擎，比如说去年毕业生的成绩信息啦。

二叉搜索树

二叉搜索树是B-树的基础，在B-树之上又进行了改进，也就是我们经常说的B+树
具体理解可以参考这篇文章 平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了

“N叉树“ 的B+树能够让一个查询尽量少地读磁盘，以InnoDB的一个整数字段索引为例，这个N差不多是1200。这棵树高是4的时候，就可以存1200的3次方个值，这已经17亿了。考虑到树根的数据块总是在内存中的，一个10亿行的表上一个整数字段的索引，查找一个值最多只需要访问3次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。
B+树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

当然不管是哈希还是有序数组，或者N叉树，它们都是不断迭代、不断优化的产物或者解决方案。

数据库技术发展到今天，跳表、LSM树等数据结构也被用于引擎设计中，有兴趣可以谷歌一下。

我们心里要有个概念，数据库底层存储的核心就是基于这些数据模型的。每碰到一个新数据库，我们需要先关注它的数据模型，这样才能从理论上分析出这个数据库的适用场景。

InnoDB 的索引模型

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。
下面来看一条SQL语句

create table Student(
id int primary key, 
score int not null, 
name varchar(16),
index (k))engine=InnoDB;

插入五条数据
1 100 s1
2 200 s2
3 300 s3
5 500 s5
6 600 s6

图示：
ID的索引

score 索引

我们需要明确一个概念：
主键索引的叶子节点存的是整行数据。在InnoDB里，主键索引也被称为聚簇索引（clustered index）。
非主键索引的叶子节点内容是主键的值。在InnoDB里，非主键索引也被称为二级索引（secondary index）。

下面来看看基于主键索引和普通索引的查询的区别之处：

select * from Student where ID=3

这是主键查询方式，则只需要搜索ID这棵B+树；

elect * from Student where score=500

即普通索引查询方式，则需要先搜索score索引树，得到的ID值为5，再到ID索引树搜索一次。这个过程称为回表。

这个务必要好好理解！！！

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

下面来看看索引的维护：

B+树为了维护索引有序性，在插入新值的时候需要做必要的维护，但是可能会出现糟糕的情况是，如果要插入数据的时候发现数据页已经满了，根据B+树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。
除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约50%。

当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

但是有一种情况能够很好的避免这种事情：主键是递增的。可以看一下自增主键：

自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的： NOT NULL PRIMARY KEY AUTO_INCREMENT。
插入新记录的时候可以不指定ID的值，系统会获取当前ID最大值加1作为下一条记录的ID值。
也就是说，自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。

而有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。

除了考虑性能外，我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？
由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约20个字节，而如果用整型做主键，则只要4个字节，如果是长整型（bigint）则是8个字节。

显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。

所以，从性能和存储空间方面考量，自增主键往往是更合理的选择。

当然也有适合用业务字段直接做主键：
只有一个索引，该索引必须是唯一索引。
由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。

这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。

下面看看关于索引的优化

首先看看覆盖索引：
以刚才的图为例

select ID from Student where score between 300 and 500

实际上这条语句直接通过score索引(辅助索引也称为二级索引或者非聚簇索引）查找ID(聚集索引也称为主键索引)，而不需要查询聚集索引中的记录。也就是没有回表。这样可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

其实覆盖索引概念很简单有没有，就是建立了辅助索引，通过辅助索引查找主键索引的值，直接能够找到，没有回表的情况而已。
当然它也有技术深度在里面
参考MySQL 覆盖索引

最左前缀原则
如果为每一种查询都设计一个索引，索引太多了，占用空间不说，还可能导致效率的下降。但是没有索引的话，你又在这个没有索引的值上查找，会引起全表扫描导致性能下降。

但是B+树这种索引结构非常好，可以利用索引的“最左前缀”，来定位记录。 最左前缀与联合索引息息相关

MySQL中的索引可以以一定顺序引用多列，这种索引叫作联合索引。
User(name,city,street)
如User表的name和city加联合索引就是 (name,city)
而最左前缀原则指的是，如果查询的时候查询条件精确匹配索引的左边连续一列或几列，则此列就可以被用到。如下：

select * from user where name=xx and city=xx ; ／／可以命中索引
select * from user where name=xx ; // 可以命中索引
select * from user where city=xx; // 无法命中索引       

顺序很重要

在建立联合索引的时候，如何安排索引内的字段顺序也是很重要的
这里我们的评估标准是，索引的复用能力。因为可以支持最左前缀，所以当已经有了(a,b)这个联合索引后，一般就不需要单独在a上建立索引了。因此，第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

关于联合索引基础知识可以参考 联合索引的基本知识

索引下推

懂得了最左前缀原则,还是不够的, 有时候还可能遇到还可以进一步优化的情况.

以 百姓表people的联合索引（name, age）为例。如果现在有一个需求：检索出表中“名字第一个字是张，而且年龄是20岁的所有壮丁”。那么，SQL语句是这么写的：

select * from people where name like '张%' and age=20 and ismale=1;

你已经知道了前缀索引规则，所以这个语句在搜索索引树的时候，只能用 “张”，找到一些满足条件的记录
然后是判断其他条件是否满足。
在MySQL 5.6之前，只能从查找的记录开始一个个回表。到主键索引上找出数据行，再对比字段值。
类似下图:

在(name,age)索引里面我特意去掉了age的值，这个过程InnoDB并不会去看age的值，只是按顺序把“name第一个字是’张’”的记录一条条取出来回表。因此，需要回表4次。

而MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

在这张图中,InnoDB在(name,age)索引内部就判断了age是否等于10，对于不等于10的记录，直接判断并跳过。在我们的这个例子中，只需要对ID4、ID5这两条记录回表取数据判断，就只需要回表2次。