目录

一.B树介绍

1.B树是什么

2.B-树介绍

3.B+树介绍

二.索引介绍

1.索引为什么能加快查询

2.MySQL索引有哪些

3.为什么不在每列都创建一个索引

4.什么地方建立索引

5.聚簇索引和非聚簇索引（都通过B+树实现）

1.聚簇索引和非聚簇索引有什么区别

​2.聚簇索引中主键索引和辅助索引的关系

​3.聚簇索引为什么要避免使用UUID作为主键

6.覆盖索引

7.最左匹配原则

1.什么是最左匹配原则

2.联合索引的底层实现(B+树)

一.B树介绍

1.B树是什么

B树是一种用于外部排序的数据结构，它的特点是树整体十分地矮胖，所以很适合用于磁盘系统中，可以大大地减少系统读取数据时的I/O次数。B树是B-树和B+树的统称。

2.B-树介绍

B-树是为了磁盘外部读取所提供的一种平衡多叉树。在InnoDB存储引擎中使用的是操作系统中的页（page）来存储数据，默认为16k。当数据超出了一页时，会进行多页存储，那么在每次获取特定主键下的数据时，需要多次的IO去分页查询，每一次IO都会耗费相当多的时间。但是B-树的出现解决了这个问题，它能够在尽量少的IO次数下获取到数据。

特点

B-树存在阶数m的概念,m阶的B-树需要满足以下条件：

1. 除了根节点和叶子节点之外的其他节点，其所含有的子节点数量N，(m / 2) <= N <= m
2. 每个节点都含有K个关键字（一般为主键）,关键字中携带数据， (m / 2) <= K <= m - 1;关键字之间升序排列
3. 每个节点都有K + 1个指针与关键字交替排列，分别指向主键区间为(k-1, k + 1)的子节点
4.  

如图是一个三阶的B-树: 

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

模拟查找关键字29的过程：

根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】 比较关键字29在区间（17,35），找到磁盘块1的指针P2。 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】 比较关键字29在区间（26,30），找到磁盘块3的指针P2。 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】 在磁盘块8中的关键字列表中找到关键字29。 分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

3.B+树介绍

B+树是B-树的改进版，它比B-树更适合用于外部存储。B-树需要在每个节点中携带有一定数量的键和数据，所以没一个节点所需的空间是较大的，这样会导致一页放不下那么多的节点，所以需要另开一页来存放节点，这会导致IO次数的增加，所以B+树改进了这一点。在InnoDB中使用的就是B+树索引。

特点

1. 除了叶子节点外，其他节点都不携带数据，只携带键
2. 通过双端双向链表将所有叶子节点相连
3. 其他特性和B-树一样

通过这两点优化，可以大大减少每个节点的占用的大小，并且由于叶子节点使用了双端双向链表连接起来，所以可以实现区间查询。

二.索引介绍

1.索引为什么能加快查询

索引将无序的数据按照一定的算法和数据结构组织起来，从而使得数据变得相对有序，这优化MySQL的查询效率。

2.MySQL索引有哪些

MySQL的索引可分为两类，一类是B+树索引，第二类是Hash索引。Hash索引的底层实现就是哈希表，而哈希表对于单条数据的获取都是常数时间的，所以在大多数查询都是单条数据时，推荐使用Hash索引；而其他大部分情况，例如需要区间查询，那么推荐使用B+树索引。

3.为什么不在每列都创建一个索引

1. 索引需要占用较多的物理空间
2. 在更改数据时，需要将大量的索引同时更改和维护
3. 创建和维护索引都需要耗费时间

4.什么地方建立索引

一个原则是，表的数据过少，无需建立索引，因为这样会使得创建和维护索引的开销性价比下降。

1. 在经常需要查询的字段上
2. 在经常需要使用WHRER语句的字段上
3. 在经常需要使用ORDER BY排序的字段上

5.聚簇索引和非聚簇索引（都通过B+树实现）

1.聚簇索引和非聚簇索引有什么区别

1. 聚簇索引：索引和数据放在了一起，找到了索引就找到了数据。因为聚簇索引需要和数据绑定，所以一张表只可以有一个聚簇索引，InnoDB中默认设为主键，其他在聚簇索引之上建立的索引被称为辅助索引。 InnoDB存储引擎采用的是聚簇索引实现，B+树的叶子节点使用主键+数据绑定。所以叶子节点在物理存储空间上是连续的。

2. 非聚簇索引：索引和数据分开存储，首先需要找到索引，然后再确定数据位置找到数据。MyISAM存储引擎使用的是非聚簇索引，B+树的叶子节点使用索引+真实数据地址实现的。所以叶子节点在物理存储空间上不连续。

2.聚簇索引中主键索引和辅助索引的关系

在InnoDB中，默认使用的是B+树实现的聚簇索引。一般以主键作为聚簇索引，而其他建立的索引为辅助索引。例如下表guest_table,我们在id上建立聚簇索引和在Name字段上建立一个辅助索引： 

当使用 select * from guest_table where id = 5时，可以直接通过建立于主键上的聚簇索引查询到数据：id = 5, Name = Gates, Company = Microsoft。

当使用 select * from guest_table where Name = "Ellison"时，会先通过以Name为索引的辅助索引去定位到Name为Ellison的id = 14，然后通过这个id去查询主键的聚簇索引，获取到整条数据id = 14, Name = Ellison, Company = Oracle。（上述过程也被称为回表查询,可以使用索引覆盖去避免回表查询。）

而在MyISAM实现的非聚簇索引中，辅助索引存储的不是Name与id，而是Name与真正的数据指针，所以可以直接通过辅助索引以Name为索引查询到数据，而不需要二次定位。

3.聚簇索引为什么要避免使用UUID作为主键

因为如果使用了UUID作为主键会导致在索引的中间区间添加数据，由于B+树的叶子节点是有序的，所以会导致叶子结点的重新排列，导致索引的更新。而使用自增主键的话，每次只需要在叶子节点末尾添加数据即可，不需要打乱索引。

6.覆盖索引

索引覆盖指的是仅通过索引就可以获得数据，如在查询主键，由于主键自身存在索引，那么在查到索引时代表数据（即主键）也已经查询到了。

如果select的数据列只用从索引中就能够取得，不必从数据表中读取，换句话说查询列要被所使用的索引覆盖。

select id from table

1. 在不使用where语句的情况下使用索引覆盖
2. 使用where语句时，如果where条件建立了辅助索引（不是主键），那么还需回表查询一次主键的索引，所以可以建立查询字段之间的联合索引，用以达到索引覆盖的目的。

7.最左匹配原则

1.什么是最左匹配原则

最左优先匹配，以最左边的为起点任何连续的索引都能匹配上。同时遇到范围查询(>、<、between、like)就会停止匹配。

假设建立了联合索引index(a, b, c),那么查询条件中，只要从a开始的连续条件情况都可以使用到联合索引提高查询效率：

1. where a = 1 and b = 2 and c = 3
2. where a = 1 and b = 2
3. where a = 1
4. where c = 3 and b = 2 and a = 1(自动优化顺序)

以下情况不可使用到该联合索引

1. where b = 1 and a = 2
2. where b = 1 and c = 3
3. where c = 1
4. where a = 1 and b = 2 and c <= 3(c遇到区间查询会打断联合索引查询)

2.联合索引的底层实现(B+树)

联合索引当然还是一颗B+树，只不过联合索引的健值数量不是一个，而是多个。构建一颗B+树只能根据一个值来构建，因此数据库依据联合索引最左的字段来构建B+树。 例子：假如创建一个（a,b)的联合索引，那么它的索引树是这样的：

1. where a = 1

可以看到a时有序的，此时b是无序的，所以可以直接根据a进行匹配。

2. where a = 1 and b = 2

可以看到，当a确定时，b就变成了有序的，此时可以按照之前的规则对b进行匹配。

3. where b = 1

由于b在a没有确定的时候是无序的，所以无法对b进行匹配。