索引的概念

  索引是帮助mysql高效获取数据的数据结构。它是对记录按照多个字段进行排序的一种方式。对表中的某个字段建立索引会创建另一种数据结构，其中保存着字段的值，每个值又指向与它相关的记录。这种索引的数据结构是经过排序的，因而可以对其执行二分查找，得到O(log2N)。而如果查询未经排序的字段，就得使用线性查找，即O(N)。但是，索引的缺点是占用额外的磁盘空间，如果为同一个表中的很多字段都建立索引，可能反而会使性能下降。



存储引擎

存储引擎种类

mysql的存储引擎一般分为两种，即innodb和myisam。

存储引擎的区别

在mysql5.1版本前，myisam是其默认引擎。myisam不支持事务，不支持外键，也不支持行锁。一般用于读多写少的场景。并且它的索引和数据是分开的。myisam的索引载入内存，数据缓存依赖操作系统。

而innodb是当前默认的引擎。它支持事务，支持外键，也支持行锁。基于聚簇索引，其索引和数据存储在一起，一起载入innodb缓冲池。



索引的类别

b树与b+树

在讲索引的类别前，我们先来讲一下索引的结构。索引采用的是b+树的结构。了解b+树之前，我们先讲一下b树。

b树是一种多叉树，或者说是一种平衡多路搜索树。它的每个节点都存储索引和数据。且节点的关键字（索引），从左到右，依次递增。查找的时候，利用二分法，可以快速地定位到查找的节点。由于节点关键字比起二叉树增多，则可以减少树的层级，也减少了查询的次数。

b+树以b树为基础，做了改进。b+树在非叶子节点上，只做数据索引，不存储数据。所有的数据都存储在叶子节点上，而用链表相连。这样便于范围查找和遍历。而因为非叶子节点不存储数据，所以每个节点能存储的关键字更多，更能减少层级。另外，索引是存储在磁盘上，由于b+树不存储数据，索引更小，非叶子节点可以存储更多的索引。这样树形比b树更加矮，更加减少io次数。

b+树的查找和插入

b+树的查找

b+树在查询的时候，从根节点开始，为第一次磁盘io，根据二分法，决定往下一阶的左还是右访问。接着做第二次磁盘io……重复此操作，直到最底层的叶子节点，然后通过链表顺序访问节点，查找到目标。

对于b+树来说，每次查找都有相同的磁盘io操作次数，每次查找都需要从根节点走到叶子节点。在进行范围查询的时候，首先查找起始节点，查找方法同上。当查找到起始节点后，直接通过叶子节点间的链表往后遍历，直到遇到结束节点。

b+树的插入

b+树在插入的时候。分为4种情况。

  • 如果插入的关键字所在的叶子节点，其关键字数小于阶数，则直接插入。
  • 如果插入的关键字所在的叶子节点，其关键字数等于阶数，且父节点的关键字数小于阶数。则将叶子节点分裂为 阶数/2 的两个部分。并把关键字上移到父节点。
  • 如果插入的关键字所在的叶子节点，其关键字数等于阶数，且父节点的关键字数等于阶数。则在完成上述操作后，继续分裂节点，并把关键字向上移动，直到节点的关键字不大于阶数。
  • 如果插入的关键字比节点中最大的关键字还大，则把最大的关键字替换，然后依次往下，把这个关键字加到叶子节点中。
b+树的删除

b+树在删除的时候。分为3种情况。

  • 如果删除的关键字所在的叶子节点，其关键字数大于阶数/2，则可以直接删除该关键字。
  • 如果删除的关键字是叶子节点的最大/最小关键字，则删除该关键字后，需要向上替换所有父节点的最大/最小关键字。
  • 如果删除的关键字所在的叶子节点，其关键字数小于阶数/2。则分情况讨论，如果旁边的兄弟节点，其关键字数等于阶数，则可以借一个关键字，同时修改该节点及其父节点的最大/最小关键字。如果兄弟节点没有多余的关键字，则与兄弟节点合并，之后也同样去修改该节点及其父节点的最大/最小关键字。如果父节点的关键字数也不满足要求，则同样和兄弟节点借关键字或者合并，如此操作，最终满足b+树的规则即可。

聚簇索引与非聚簇索引

聚簇索引

innodb基于聚簇索引。其主键索引会以主键建立索引，如果没有主键，则会以一个非空的唯一索引建立。如果都没有，则会自己产生一个隐藏列id来建立主键索引。

在聚簇索引的主键索引中，其数据都存储在叶子节点上。而其辅助索引中，叶子节点存储的是主键值，所以当辅助索引查找到叶子节点时，需要再到主键索引中去查找数据，这就是回表。但并不是所有情况都会回表。当发生覆盖索引（即查询的字段都包含在索引列中）时，不需要回表。

一个表只有一个聚簇索引。因为其物理存储顺序与索引顺序是一致（但并不是物理上连续的，而是逻辑上连续的）。即只要索引是相邻的，那么对应的数据一定也是相邻地存储在磁盘上的。

所以，对于innodb的主键，我们尽量设置其为顺序递增的数字。因为其同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放。这样，每当一条新的记录插入时，会被顺序添加到当前索引节点的后续位置。每一页写满，则会开辟一个新的页，形成一个紧凑的结构，近似顺序填充。这样插入时也不需要移动已有的数据，很少开销，提供了效率。

非聚簇索引

myisam基于非聚簇索引。它的索引和数据都是分开的。它的主键索引和辅助索引是独立的，只是主索引的key必须唯一，辅助索引的key可以重复，搜索时辅助索引无需访问主索引树。其叶子节点上存储的都是数据文件的地址指针。所以非聚簇索引比聚簇索引多了一次读取数据的IO操作。