数据库为什么须要索引呢？

咱们都是晓得数据库的数据都是存储在磁盘上的，当咱们程序启动起来的时候，就相当于一个过程运行在了机器的内存当中。所以当咱们程序要查问数据时，必须要从内存进去到磁盘外面去查找数据，而后将数据写回到内存当中。然而磁盘的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创立联结索引的规定是首先会对联结索引的最右边第一个字段排序，在第一个字段的排序根底上，而后在对第二个字段进行排序。