索引是怎样工作的？
索引的出现是提高数据查询效率，就像教科书中的目录一样。
索引的常见模型
-
哈希表
-
哈希表是一种以键值存储的结构，我们只需要输入待查找的键即为key，就可以找到对应的值Value.哈希的思路很简单，把值放大数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置
-
多个key值经过哈希函数换算，会出现同一个值的情况。处理这种情况的方法是拉链法
-
哈希索引做区间查询的速度很慢
-
哈希表这种结构适用于等值查询场景，比如Memcached及其他一些，NoSQL引擎
-
-
有序数组
-
有序数组在等值查询和范围查询场景性能都非常优秀
-
如果使用有序数组使用身份证号递增的顺序，按照二分法查询，如果从查询效率，有序数组是最好的，但是插入一个记录需要挪动后面所有的记录成本太高
-
有序数组适用于静态存储引擎
-
-
搜索树
- 二叉搜索树:父节点的左子树所有节点的值小于父节点的值，右子树所有节点的值大于父节点的值，为了维持O(log(N))的时间复杂度，就需要保证这棵树更新时间复杂度为O(log(N))
- 二叉树的搜索效率是最高的，但是实际大多数的数据库存储却不使用二叉树，其原因。索引不止存在内存中，还要写在磁盘上。
- 如果一棵树100万个节点的平衡二叉树，树高20.一次查询可能需要访问20个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要10ms左右的寻址空间，也就是说，对于100万行表，如果使用二叉树来存储，单独访问一个行可能需要20个10ms，这个查询速度太慢了
- 为了减少查询尽量少的读取磁盘，就必须查询过程访问尽量少的数据块，那么，我们就不该用二叉树，而是用N叉树
以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘
N叉树由于读写上的性能特点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中
Innodb索引模型
-
Innodb中表根据主键顺序以索引方式存放的，这种存储方式的表为索引组织表，Innodb使用B+树索引模型，所以数据都是存储在B+树中
-
每一个索引在Innodb里面对应一棵B+树
-
主键索引叶子节点存放的是整行数据，二级索引叶子节点存储的是二级索引
基于主键索引和普通索引的查询区别是什么？
- 根据主键索引查询方式，只需要搜索ID这棵树B+树
- 则需要先搜索K索引树，得到ID值500，再到ID索引树搜索一次，这个过程称为回表
索引维护
B+树为了维护索引有序性，在插入新值的时候需要必要的维护
-
如果插入ID为700直接在R5后面插入即可，如果插入400需要逻辑上面挪动后面的数据，如果R5所在数据页已经满了，根据B+树算法，这时候需要申请一个数据页，然后挪动部分数据过去，这个过程叫做页分裂，这种情况下性能会下降
-
除了性能外，页分裂操作还会影响数据页利用率，原本放在一个页的数据分为两页，整体空间利用率降低50%
-
当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。
-
自增主键每次插入一条新纪录都是追加操作，都不涉及到挪动其他记录，也不会触发叶分裂
-
只有一个索引，该索引必须是唯一索引的时候可以考虑业务字段作为主键
Innodb使用了B+树结构，B+树能够很好地配合磁盘读写特性，减少单次查询磁盘访问次数。由于Innodb是索引组织表，一般情况下我会建议你创建一个自增主键，这样非主键索引占用空间最小
- 由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段
最左前缀原则
B+树这种索引结构，可以利用索引的最左前缀，来定位记录，联合索引考虑空间与复用
索引下推
检索出表中“名字第一个字是张，而且年龄是 10 岁的所有男孩”。那么，SQL 语句是这么写的：
mysql> select * from tuser where name like '张%' and age=10 and ismale=1;
Mysql5.6引入索引下推优化，可以索引遍历过程中，对索引包含的字段先做判断，直接过滤掉不满足的记录，减少汇报次数。InnoDB在(name,age)索引下推的过程中判断age的存在，减少一次次数