共计 2686 个字符，预计需要花费 7 分钟才能阅读完成。
数据库为什么须要索引呢？
咱们都是晓得数据库的数据都是存储在磁盘上的，当咱们程序启动起来的时候，就相当于一个过程运行在了机器的内存当中。所以当咱们程序要查问数据时，必须要从内存进去到磁盘外面去查找数据，而后将数据写回到内存当中。然而磁盘的 io 效率是远不如内存的，所有查找数据的快慢间接影响程序运行的效率。
而数据库加索引的次要目标就是为了应用一种适合的数据结构，能够使得查问数据的效率变高，缩小磁盘 io 的次数，晋升数据查找的速率，而不再是愣头青式的全局遍历。
那索引为啥要用 B +Tree 的数据结构呢？
如果咱们简略的想的话，想要疾速的查找到数据，感觉 hash 表是最快的，依据 key，hash 到某个槽位上，间接一次查找就能够精确的找到数据的地位，这多快呀。然而咱们在做业务时，往往只须要一条的数据需要很少，大部分的需要都是依据肯定的条件查问一部分的数据，这个时候 hash 显示不是很适合。
咱们再思考树，比方二叉树，均衡二叉树，红黑树，B 树等，他们都是二分查找，找数也快，然而不论是均衡二叉树还是优化后的红黑树，说到底他们都是二叉树，当节点多了的时候，它们的高度就会高呀，我找一个数据。根节点不是，那就找下一层，下一层还没有我就再去找下一层，这样造成的结果就是我找一个数据可能要找好几次，而每一次都是执行了一次磁盘的 io，而咱们的索引的目标就是要缩小磁盘 io 呀，这样设计可不行。那咱们是不是把高度变矮就能够了呢？
所以咱们再思考下 B 树。首先简略介绍下 B 树的数据结构：
首先看看 B 树的定义。
- 每个节点最多有 m - 1 个关键字（能够存有的键值对）。
- 根节点起码能够只有 1 个关键字。
- 非根节点至多有 m / 2 关键字。
- 每个节点中的关键字都依照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
- 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都雷同。
- 每个节点都存有索引和数据，也就是对应的 key 和 value。
所以，根节点的 关键字 数量范畴：1 <= k <= m-1，非根节点的 关键字 数量范畴：m/2 <= k <= m-1。
这里的 m 示意阶数，阶数示意了一个节点最多有多少个孩子节点，所以形容一颗 B 树时须要指定它的阶数。
咱们再举个例子来阐明一下下面的概念，比方这里有一个 5 阶的 B 树，根节点数量范畴：1 <= k <= 4，非根节点数量范畴：2 <= k <= 4。
上面，咱们通过一个插入的例子，解说一下 B 树的插入过程，接着，再解说一下删除关键字的过程。
1.2 B 树插入
插入的时候，咱们须要记住一个规定：判断以后结点 key 的个数是否小于等于 m -1，如果满足，直接插入即可，如果不满足，将节点的两头的 key 将这个节点分为左右两局部，两头的节点放到父节点中即可。
例子：在 5 阶 B 树中，结点最多有 4 个 key, 起码有 2 个 key（留神：上面的节点对立 用一个节点示意 key 和 value）。
- 插入 18，70，50,40
- 插入 22
插入 22 时，发现这个节点的关键字曾经大于 4 了，所以须要进行决裂，决裂的规定在下面曾经讲了，决裂之后，如下。
- 接着插入 23，25，39
决裂，失去上面的。
所以 B 树每一层的节点数会变多，雷同的数据量的话，B 树会比二叉树高度更低，须要的 io 次数就会变少，所以合乎咱们的索引需要。那 MySQL 最初为什么抉择了 B + 树呢，比 B 树更优的中央在哪里呢？
咱们先看看 B + 树与 B 树不同的中央：
- B+ 树叶子节点蕴含了这棵树的所有键值，非叶子节点不存储数据，只存储索引，数据都存储在叶子节点。而 B 树是每个节点都存有索引和数据。
- B+ 树每个叶子结点都存有相邻叶子结点的指针，叶子结点自身依关键字的大小自小而大程序链接。
如图：
第一点：当非叶子节点只存索引 key 而不存 data 时，就能够使得非叶子节点的占用空间变少，雷同容量的节点能够存储更多的索引，那同样是三层的 B + 树，阶数就会变多，就会比 B 树存更多的数据。
第二点：B+ 树叶子节点存有相邻叶子节点的指针，想要了解这个指针的益处，咱们的先晓得磁盘读取数据时往往不是严格按需读取，而是每次都会 预读，即便只须要一个字节，磁盘也会从这个地位开始，程序向后读取肯定长度的数据放入内存。这样做的理论依据是计算机科学中驰名的局部性原理：
- 当一个数据被用到时，其左近的数据也通常会马上被应用。
- 程序运行期间所须要的数据通常比拟集中。
预读的长度个别为页（page）的整倍数 。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区宰割为间断的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为 4k），主存和磁盘以页为单位替换数据。当程序要读取的数据不在主存中时，会触发一个缺页异样，此时零碎会向磁盘收回读盘信号，磁盘会找到数据的起始地位并 向后间断读取 一页或几页载入内存中，而后异样返回，程序持续运行。
当初再看 B + 树叶子节点的指针，咱们就明确了它的用途，预读的时候能够保障间断读取的数据有序。
可能还有的同学提过 B * 树，它是在 B + 树根底上，为非叶子结点也减少链表指针。集体感觉没用 B 星树可能是感觉没必要吧，咱们在非叶子节点又不存 data，data 都在叶子节点，非叶子节点了链表指针用不上。
一些花里胡哨的概念
聚簇索引和非聚簇索引：下面咱们提到 B + 树的叶子节点存了索引 key 的数据 data，然而 mysql 不同的引擎存 data 的抉择是不一样的，MyISAM 是将索引文件和实在的数据文件分两个文件各种寄存，索引文件中存的 data 是该索引 key 对应的数据在数据文件中的地址值，而 InnoDB 则是将正式的数据存在了叶子节点中。所以聚簇和非聚簇就是辨别叶子节点存的 data 是不是实在的（能够了解为叶子节点挤不挤？）
回表：回表也简略，然而得先明确主键索引和一般索引，下面咱们所的叶子节点存实在的数据，那是只有主键索引才是这么存的，一般索引它存的 data 是主键索引的 key。那这样咱们就好了解了。比方我当初给一张表的 name 字段建了个一般索引，我想 select * from table where name = ‘test’，这个时候咱们找到 test 节点的时候，拿到的 key 只是这行数据对应的主键 key，咱们要失去整行的数据只能拿着这个 key 再去主键索引树再找一次。这个操作就叫做回表。
最左匹配准则：当咱们新建了一个组合索引时，比方（name+age），查问时应用 where name = xx and age = xx 时会走组合索引，而 where age = xx and name =xx 则不会走。这是因为 MySQL 创立联结索引的规定是首先会对联结索引的最右边第一个字段排序，在第一个字段的排序根底上，而后在对第二个字段进行排序。
