MySQL索引，B+树和B-树

索引是什么?

索引是帮助MySQL高效获取数据的数据结构。

索引能干什么?

提高数据查询的效率。

索引：排好序的快速查找数据结构！索引会影响where后面的查找，和order by 后面的排序。

索引的分类

1.从存储结构上来划分：BTree索引（B-Tree或B+Tree索引），Hash索引，full-index全文索引，R-Tree索引。描述的是索引存储时保存的形式。

2.从应用层次来分：普通索引，唯一索引，复合索引。

3.根据数据的物理顺序与键值的逻辑（索引）顺序关系：聚集索引，非聚集索引。

普通索引：即一个索引只包含单个列，一个表可以有多个单列索引
唯一索引：索引列的值必须唯一，但允许有空值
复合索引：即一个索引包含多个列
聚簇索引(聚集索引)：并不是一种单独的索引类型，而是一种数据存储方式。具体细节取决于不同的实现，InnoDB的聚簇索引其实就是在同一个结构中保存了B-Tree索引(技术上来说是B+Tree)和数据行。
非聚簇索引：不是聚簇索引，就是非聚簇索引。

索引的底层实现：

mysql默认存储引擎innodb只显式支持B-Tree( 从技术上来说是B+Tree)索引，对于频繁访问的表，innodb会透明建立自适应hash索引，即在B树索引基础上建立hash索引，可以显著提高查找效率，对于客户端是透明的，不可控制的，隐式的。

Hash索引

基于哈希表实现，只有精确匹配索引所有列的查询才有效，对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），并且Hash索引将所有的哈希码存储在索引中，同时在索引表中保存指向每个数据行的指针。

B-Tree能加快数据的访问速度，因为存储引擎不再需要进行全表扫描来获取数据，数据分布在各个节点之中。

是B-Tree的改进版本，同时也是数据库索引索引所采用的存储结构。数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都指向相邻的叶子节点的地址。相比B-Tree来说，进行范围查找时只需要查找两个节点，进行遍历即可。而B-Tree需要获取所有节点，相比之下B+Tree效率更高。

案例：假设有一张学生表，id为主键

在MyISAM引擎中的实现（二级索引也是这样实现的）

在InnoDB中的实现

三、问题

问：为什么索引结构默认使用B-Tree，而不是hash，二叉树，红黑树？

hash：虽然可以快速定位，但是没有顺序，IO复杂度高。

二叉树：树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），并且IO代价高。

红黑树：树的高度随着数据量增加而增加，IO代价高。

问：为什么官方建议使用自增长主键作为索引。

结合B+Tree的特点，自增主键是连续的，在插入过程中尽量减少页分裂，即使要进行页分裂，也只会分裂很少一部分。并且能减少数据的移动，每次插入都是插入到最后。总之就是减少分裂和移动的频率。

B树

B树也称B-树,它是一颗多路平衡查找树（并不一定是二叉树）。

每个节点最多有m-1个关键字（可以存有键值对）
根节点最少可以只有1个关键字
非根节点至少有m/2个关键字
每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中所有的关键字都小于它，而右子树中的所有关键字都大于它
所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同
每个节点都存有索引和数据，也就是对应的key和value

所以，根节点的关键字数量范围：1 <= k <= m-1，非根节点的关键字数量范围：m/2 <= k <= m-1。

描述一颗B树时需要指定它的阶数，阶数表示了一个节点最多有多少个孩子节点，一般用字母m表示阶数。

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树，然后进行删除操作

删除15，这种情况是删除叶子节点的元素，如果删除之后，节点数还是大于m/2，这种情况只要直接删除即可。

接着，我们把22删除，这种情况的规则：22是非叶子节点，对于非叶子节点的删除，我们需要用后继key（元素）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。对于删除22，需要将后继元素24移到被删除的22所在的节点。

此时发现26所在的节点只有一个元素，小于2个（m/2），这个节点不符合要求，这时候的规则（向兄弟节点借元素）：如果删除叶子节点，如果删除元素后元素个数少于（m/2），并且它的兄弟节点的元素大于（m/2），也就是说兄弟节点的元素比最少值m/2还多，将先将父节点的元素移到该节点，然后将兄弟节点的元素再移动到父节点。这样就满足要求了。

我们看看操作过程就更加明白了。

接着删除28，删除叶子节点，删除后不满足要求，所以，我们需要考虑向兄弟节点借元素，但是，兄弟节点也没有多的节点（2个），借不了，怎么办呢？如果遇到这种情况，首先，还是将先将父节点的元素移到该节点，然后，将当前节点及它的兄弟节点中的key合并，形成一个新的节点。

移动之后，跟兄弟节点合并。

删除就只有上面的几种情况，根据不同的情况进行删除即可。

B+树

B+树其实和B树是非常相似的，我们首先看看相同点。

根节点至少一个元素
非根节点元素范围：m/2 <= k <= m-1

不同点。

B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存储在叶子节点。
内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
父节点存有右孩子的第一个元素的索引。