作者：王新华
为什么须要索引？
一句话概括：索引的呈现其实就是为了进步数据查问的效率。
一、索引常见模型
模型：哈希表、有序数组和搜寻树
哈希表
- 哈希表是一种以键 – 值（key-value）存储数据的构造，咱们只有输出待查找的键即 key，就能够找到其对应的值即 Value。哈希的思路很简略，把值放在数组里，用一个哈希函数把 key 换算成一个确定的地位，而后把 value 放在数组的这个地位。
工夫复杂度：0(1) - 画重点：如果索引的值有反复的话，会产生 hash 碰撞，尽管能够解决 hash 抵触，然而导致查问效率升高。
- 场景：哈希表这种构造实用于只有等值查问的场景，不适用于查找范畴的。相似 redis Memcached 及其他一些 NoSQL 引擎。
搜寻树
在理解搜寻树之前咱们须要先晓得 二叉树、均衡二叉树、B 树、B+ 树
举荐一个工具能够清晰的了解树的原理：https://www.cs.usfca.edu/~gal…
二叉树
二叉树个性：左子树的键值小于根的键值，右子树的键值大于根的键值。
如下图就是一个二叉树
以后二叉树的插入程序是：3 2 4 1 5
如果咱们按 1 2 3 4 5 的程序来插入的化，咱们失去的二叉树就是如下图所示
如果是这种二叉树查问效率就太低了。若想二叉树的查问效率尽可能高，须要二叉树是均衡的从而引出新的定义 – 均衡二叉树或称 AVL 树。
均衡二叉树
均衡二叉树特点：
- 满足二叉树的个性
- 任何节点的两个子树的高度最大差为 1
如上两个组合之后就是均衡二叉树，如下图
中插入树的程序为：1 2 3 4 5 6 7 8 时候生成的是如图所示的内容，和图二实现不一样，在通过工具生成这个图的时候显著能够看到不论如何插入节点数据都能满足均衡二叉树的特点 2。
当删除一个节点之后同样能满足 avl 树，如下图删除图 3 中的 5 节点之后展现如下。
总结一下 均衡二叉树的长处
- a 不错的查找性能（O（logn）), 不存在极其的低效查找的状况。
- b 能够实现范畴查找、数据排序。
看起来 AVL 树作为数据查找的数据结构的确很不错，然而 AVL 树并不适宜做 Mysql 数据库的索引数据结构，因为考虑一下这个问题：
数据库查问数据的瓶颈在于磁盘 IO，如果应用的是 AVL 树，咱们每一个树节点只存储了一个数据，咱们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比方查问 id=8 这个数据咱们就要进行磁盘 IO 三次，这是如许耗费工夫的。所以咱们设计数据库索引时须要首先思考怎么尽可能减少磁盘 IO 的次数。
磁盘 IO 有个有个特点，就是从磁盘读取 1B 数据和 1KB 数据所耗费的工夫是根本一样的，咱们就能够依据这个思路，咱们能够在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+ 树的的设计原理了。
B- 树
B 树的特点：
- 所有健值散布在整棵树中
- 搜寻有可能在非叶子节点完结
- 根节点至多有 2 个子树
- 所有叶子节点都在同一层
- 分叉数（路数）永远比要害字数多 1
- 节点存储 key 和 value
演示 B 树索引决裂合并
比方 Max Degree（路数）是 3 的时候，咱们插入数据 1、2、3，在插入 3 的时候，原本应该在第一个磁盘块，然而如果一个节点有三个关键字的时候，意味着有 4 个指针，子节点会变成 4 路，所以这个时候必须进行决裂。把两头的数据 2 提上去，把 1 和 3 变 成 2 的子节点。
如果删除节点，会有相同的合并的操作。留神这里是决裂和合并，跟 AVL 树的左旋和右旋是不一样的。咱们持续插入 4 和 5，B Tree 又会呈现决裂和合并的操作。
从这个外面咱们也能看到，在更新索引的时候会有大量的索引的构造的调整，节点的决裂和合并，其实就是 InnoDB 页的决裂和合并。
B+ 树
B+ 树是在 B 树上做的一个优化工作
- B+ 树每个节点能够蕴含更多的节点内容，为什么这么做呢？第一：升高树的高度 第二：将数据范畴变为多个区间，区间越多 检索速度就越快
- 非叶子节点存的是 key, 叶子节点存的是 key 和数据
- 叶子节点指针相连，程序查找速度更快
B 树和 B+ 树有什么不同呢？
第一，B 树一个节点里存的是 key 和数据，而 B+ 树存储的是索引（地址），所以 B 树里一个节点存不了很多个数据，然而 B+ 树一个节点能存很多索引，B+ 树叶子节点存所有的数据。
第二，B+ 树的叶子节点是数据阶段用了一个链表串联起来，便于范畴查找。
通过 B 树和 B+ 树的比照咱们看出，B+ 树节点存储的是索引，在单个节点存储容量无限的状况下，单节点也能存储大量索引，使得整个 B+ 树高度升高，缩小了磁盘 IO。其次，B+ 树的叶子节点是真正数据存储的中央，叶子节点用了链表连接起来，这个链表自身就是有序的，在数据范畴查找时，更具备效率。因而 Mysql 的索引用的就是 B+ 树，B+ 树在查找效率、范畴查找中都有着十分不错的性能。
综上所述 mysql innodb 索引抉择了 B + 树。
思考问题
1、B+ 树叶子节点存的诗所有数据，如果 1000 万数据，那这个链表太大，不会影响性能吗？
能够利用数据页，上面有重点剖析
2、InnoDB 一棵 B + 树能够寄存多少行数据？
B+Tree 的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。搜寻 到关键字不会间接返回，会到最初一层的叶子节点。比方咱们搜寻 id=3，尽管在第一 层间接命中了，然而全副的数据在叶子节点下面，所以我还要持续往下搜寻，始终到叶 子节点。
举个例子：假如一条记录是 1K，一个叶子节点（一页）能够存储 16 条记录。非叶 子节点能够存储多少个指针？
假如索引字段是 bigint 类型，长度为 8 字节。指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节。非叶子节点（一页）能够存储 1024*16 / 14 = 1170 个这样的 单元（键值 + 指针），代表有 1170 个指针。
树深度为 2 的时候，有 1170^2 个叶子节点，能够存储的数据为：
1170 * 1170 * 16 = 21902400 2000 万
在查找数据时一次页的查找代表一次 IO，也就是说，一张 2000 万左右的表，查问数据最多须要拜访 3 次磁盘。所以在 InnoDB 中 B+ 树深度个别为 1-3 层，它就能满足千万级的数据存储。
二、innodb 的索引剖析
在 InnoDB 中，表都是依据主键程序以索引的模式寄存的，这种存储形式的表称为索引组织表。
上述中咱们从不同维度剖析了最终 InnoDB 应用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。
每一个索引在 InnoDB 外面对应一棵 B+ 树。假如，咱们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有一般索引。
这个表的建表语句是：
create table user(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;表中 第一行到第五行 的 (ID,k) 值别离为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。
上图为：主健索引
上图为：一般索引
依据下面的索引构造阐明，咱们来探讨一个问题：基于主键索引和一般索引的查问有什么区别？
如果语句是 select * from T where ID=500，即主键查问形式，则只须要搜寻 ID 这棵 B+ 树；
如果语句是 select * from T where k=5，即一般索引查问形式，则须要先搜寻 k 索引树，失去 ID 的值为 500，再到 ID 索引树搜寻一次。这个过程称为回表。也就是说，基于非主键索引的查问须要多扫描一棵索引树。因而，咱们在利用中应该尽量应用主键查问。
B+ 树为了保护索引有序性，在插入新值的时候须要做必要的保护。以下面这个图为例，如果插入新的行 ID 值为 700，则只须要在 R5 的记录前面插入一个新记录。如图
如果新插入的 ID 值为 400，就绝对麻烦了，须要逻辑上移动前面的数据，空出地位，如图。
而更糟的状况是，如果 R5 所在的数据页曾经满了，依据 B+ 树的算法，这时候须要申请一个新的数据页，而后移动局部数据过来。这个过程称为页决裂。在这种状况下，性能天然会受影响。
除了性能外，页决裂操作还影响数据页的利用率。本来放在一个页的数据，当初分到两个页中，整体空间利用率升高大概 50%。当然有决裂就有合并。
当相邻两个页因为删除了数据，利用率很低之后，会将数据页做合并。合并的过程，能够认为是决裂过程的逆过程。
三、innodb 数据页
在上述中咱们提到数据页，数据页的概念，它是 MySQL 治理存储空间的根本单位，一个页的大小个别是 16KB，并且咱们晓得了记录其实是被寄存在页中的，如果记录占用的空间太大还可能造成行溢出景象，这会导致一条记录被扩散存储在多个页中。
页的实质就是一块 16KB 大小的存储空间，InnoDB 为了不同的目标而把页分为不同的类型，其中用于寄存记录的页也称为数据页，咱们先看看这个用于寄存记录的页长什么样。数据页代表的这块 16KB 大小的存储空间能够被划分为多个局部，不同局部有不同的性能，各个局部如图所示：
从图中能够看出，一个 InnoDB 数据页的存储空间被划分成了 7 个局部，每个局部又能够被划分为若干小局部。
上面用数据页来剖析 innodb 索引数据.
咱们已主键索引为例子，每一页默认大小 16k，当咱们第一页用户数据区域页满了的时候 就会进行申请新的页也就是第二页 而后有新的数据插入时候会在第二页中存入咱们的用户数据比方如图中的 R4，波及到这种数据的检索页内的数据是相似一个链表，页与页之间也是链表，当数据量大的时候其实性能比拟差的，这个时候咱们须要引入页目录的概念。
当有了页目录之后检索性能会晋升很多，然而如果页很多的时候其实性能也会存在弊病，那这个时候须要如何解决呢，这个时候咱们须要在下层在