一、什么是索引

索引（Index）是帮助数据库高效获取数据的数据结构。索引是在基于数据库表创建的，它包含一个表中某些列的值以及记录对应的地址，并且把这些值存储在一个数据结构中。

使用索引的原因：数据库查询是数据库最主要的功能之一。而查询速度当然是越快越好。而当数据量越来越大的时候，查询花费的时间会随之增长。而索引，可以加速数据的查询。因为索引是有序排列的。

二、为什么 Mysql 用 B + 树做索引而不用 B 树或红黑树

** mysql索引是排好序的B+tree，所有节点在叶子节点，叶子节点为双向链表，同时叶子节点还加了指针**。

B + 树所有的 Data 域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。在数据库中基于范围的查询是非常频繁的，而 B 树不支持这样的遍历操作。

1.1为什么不用红黑树**

    1. 节点是红色或黑色。
    1. 根节点是黑色。
  • 3 每个叶节点（NIL节点，空节点）是黑色的。
  • 4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    1. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

例：
圖片.png红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构，这是因为使用 B+ 树访问磁盘数据有更高的性能。

（一）B+ 树有更低的树高 平衡树的树高 O(h)=O(logdN)，其中 d 为每个节点的出度。红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多。

（二）磁盘访问原理：操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。如果数据不在同一个磁盘块上，那么通常需要移动制动手臂进行寻道，而制动手臂因为其物理结构导致了移动效率低下，从而增加磁盘数据读取时间。B+ 树相对于红黑树有更低的树高，进行寻道的次数与树高成正比，在同一个磁盘块上进行访问只需要很短的磁盘旋转时间，所以 B+ 树更适合磁盘数据的读取。

（三）磁盘预读特性：为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。并且可以利用预读特性，相邻的节点也能够被预先载入。

1.2B-树
圖片.png
a、所有节点分布在树上，并不是都在叶子节点
b、每个节点的索引和数据在一起
c、叶子节点不互相关联
1.3B+树

圖片.png
a、非叶子节点不存储数据，只存储索引冗余，可以存放更多的索引
b、叶子节点包含所有节点数据
c、叶子节点用指针连接，提高区间访问的性能
d、叶子节点存放索引和数据 - 存放主键索引和数据，二级索引是单独的树，有时需要回表查询
注意：叶子节点为有序的双向链表

注意：mysql一页的数据是16kb，第一层的数据大小为1页（show global status like ‘Innodb page size’）, 假如主键为bigint类型，占用8个字节，白色区域（下一个节点的文件地址）占6个字节，16kb/14字节 = 1170个，第二层为 11701170，第三层叶子节点数据大小为1kb，相当于16个 11701170*16 = 2千万条多数据。B树未将数据放在叶子节点，那么每层存储的数据个数有限，那么树的高度会非常高
数据存储在叶子节点，是为了降低树的高度，当树的高度为3的时候，可存储2千万条数据，
如果不存储在叶子节点，每层可存储16条数据，则需要很多很多层，
mysql查询的速度取决于树的高度

mysql中存储索引用到的数据结构是B+树，B+树的查询跟树的高度有关，是log(n),如果用hash存储，那么查询时间是O(1)。既然hash比B+树更快，为什么mysql用B+树来存储索引呢？

（1）这和业务场景有关。如果只选一个数据，那确实是hash更快。但是数据库中经常会选择多条，这时候由于B+树索引有序，并且又有链表相连，它的查询效率比hash就快很多了；hash不适合范围查询。
（2）数据库中的索引一般是在磁盘上，数据量大的情况可能无法一次装入内存，B+树的设计可以允许数据分批加载，同时树的高度较低，提高查找效率。

1.4联合索引
圖片.png
先按name排序，name相同按照age排序，age相同则按照position排序，所以查找遵循最左前缀法则。

联合索引的最左原则：
例：student表字段：a 、b、c、d、e
a、b、c为联合索引
where a and b and c 有效
where a and c 有效
where a and b 有效
where b and c 无效
where c 无效