B/B+树

我们在MySQL中的数据一般是放在磁盘中的，读取数据的时候肯定会有访问磁盘的操作，磁盘中有两个机械运动的部分，分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟，而磁盘移动则是在盘片旋转到指定位置以后，移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程，而定位是磁盘的存取中花费时间比较大的一块，毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候，显然定位是一个非常花费时间的过程，但是我们可以通过B树进行优化，提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢？我们可以根据B类树的特点，构造一个多阶的B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后面我们可以更快的找到信息，磁盘的I/O操作也少一些，而且B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的。

总的来说，B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉，B树每个内节点有多个分支)，与红黑树相比，在相同的的节点的情况下，一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到)。B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成，而CPU的速度非常快，所以B树的操作效率取决于访问磁盘的次数，关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少

B+树的特点：

1、非叶子节点的子树指针与关键字个数相同；
2、非叶子节点的子树指针p[i],指向关键字值属于[k[i],k[i+1]]的子树.(B树是开区间,也就是说B树不允许关键字重复,B+树允许重复)；
3、为所有叶子节点增加一个链指针；
4、所有关键字都在叶子节点出现(稠密索引). (且链表中的关键字恰好是有序的)；
5、非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层；
6、更适合于文件系统；

为什么说B+树比B树更适合数据库索引？

1、 B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

2、B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3、由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

数据库索引采用B+树的主要原因是：B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。

B+树成为了数据库比较优秀的数据结构，MySQL中MyIsAM和InnoDB都是采用的B+树结构。不同的是前者是非聚集索引，后者主键是聚集索引，所谓聚集索引是物理地址连续存放的索引，在取区间的时候，查找速度非常快，但同样的，插入的速度也会受到影响而降低。聚集索引的物理位置使用链表来进行存储。

order by 和 limit 与 索引

https://blog.csdn.net/h2604396739/article/details/80535546

我们先来看2条sql

第一条：
select * from acct_trans_log WHERE acct_id = 1000000000009000757 order by create_time desc limit 0,10

第二条：
select * from acct_trans_log WHERE acct_id = 1000000000009003061 order by create_time desc limit 0,10

表的索引及数据总情况：索引：acct_id，create_time分别是单列索引，数据库总数据为500w

通过acct_id过滤出来的结果集在1w条左右

查询结果：第一条要5.018s，第二条0.016s

为什么会是这样的结果呢？第一，acct_id和create_time都有索引，不应该出现5s查询时间这么慢啊

那么先来看执行计划

第一条sql执行计划：

image

第二条执行计划：

image

仔细观察会发现，索引只使用了idx_create_time，没有用到idx_acct_id

这能解释第一条sql很慢，因为where查询未用到索引，那么第二条为什么这么快？

看起来匪夷所思，其实搞清楚mysql查询的原理之后，其实很简单

我们来看这 2条sql查询，都用到了where order by limit

当有limit存在时，查询的顺序就有可能发生变化，这时并不是从数据库中先通过where过滤再排序再limit

因为如果这样的话，即，先过滤在limit的话，从500万数据中通过where过滤就不会是5s了。

此时的执行顺序是，先根据idx_create_time索引树，从最右侧叶子节点，反序取出n条，然后逐条去跟where条件匹配

若匹配上，则得出一条数据，直至取满10条为止，为什么第二条sql要快，因为运气好，刚好时间倒序的前几条就全部满足了。

搞清楚原理之后，我们了解了为什么第一条慢，第二条快的原因，但是问题又来了

为什么mysql不用idx_acct_id索引，这是一个问题，因为这样的话，我们的建立的索引基本失效了，在此类sql下

查询效率将会是相当低。

因为通过acct_id过滤出来的结果集比较大，有上万条，mysql认为按时间排序如果不用索引，将会是filesort, 这样会很慢，而又不能2个索引都用上，所以选择了idx_create_time。

为什么mysql只用一个索引

这里为什么不能2个索引都用上，可能很多人也不知道为什么，其实道理很简单，每个索引在数据库中都是一个索引树，其数据节点存储了指向实际

数据的指针，如果用一个索引来查询，其原理就是从索引树上去检索，并获得这些指针，然后去取出数据，试想，如果你通过一个索引，得到过滤后的指针，这时，你的另一个条件索引如果再过滤一遍，将得到2组指针的集合，如果这时候取交集，未必就很快，因为如果每个集合都很大的话，取交集的时候，等于扫描2个集合，效率会很低，所以没法用2个索引。

当然有时候mysql会考虑临时建立一个联合索引，将2个索引联合起来用，但是并不是每种情况都能奏效，同样的道理，用一个索引检索出结果集之后，排序时，也无法用上另一个索引了。

实际上用索引idx_acct_id大多数情况还是要比用索引idx_create_time要快，我们举个例子：

select * from acct_trans_log force index(idx_acct_id) WHERE acct_id = 1000000000009000757 order by create_time desc limit 0,10

耗时：0.057s

可以看出改情况用idx_acct_id索引是比较快的，那么是不是这样就可以了呢，排序未用上索引，始终是有隐患的。

联合索引让where和排序字段同时用上索引

看下一条sql

select * from acct_trans_log force index(idx_acct_id) WHERE acct_id = 3095 order by create_time desc limit 0,10

耗时: 1.999s

执行计划：

image

该sql通过acct_id过滤出来的结果集有100万条，因此排序将会耗时较高，所幸这里只是取出前10条最大的然后排序

查询概况，我们发现时间基本消耗在排序上，其实这是内存排序，对内存消耗是很高的。

image

那么我们有没有其它解决方案呢，这种sql是我们最常见的，如果处理不好，在大数据量的情况下，耗时以及对数据库资源的消耗都很高，这是我们所不能接受的，我们的唯一解决方案就是让where条件和排序字段都用上索引

解决办法就是建立联合索引：alter table acct_trans_log add index idx_acct_id_create_time(acct_id,create_time)

然后执行sql:select * from acct_trans_log WHERE acct_id = 3095 order by create_time desc limit 0,10

耗时: 0.016s

image

联合索引让where条件字段和排序字段都用上了索引，问题解决了！

联合索引使用的原理

但是为什么能解决这个问题呢，这时大家可能就会记住一个死理，就是联合索引可以解决where过滤和排序的问题，也不去了解其原理，这样是不对的，因为当情况发生变化，就懵逼了，下面我们再看一个sql：

select * from acct_trans_log force index(idx_acct_id_create_time) WHERE acct_id in(3095,1000000000009000757) order by create_time desc limit 0,10

耗时：1.391s

索引还是用idx_acct_id_create_time，时间居然慢下来了

执行计划是：

image

看执行计划，排序用到了filesort，也就是说，排序未用到索引。

那么我们还是来看看，索引排序的原理，我们先来看一个sql:select * from acct_trans_log ORDER BY create_time limit 0,100

耗时：0.029s

执行计划为：

image

这里执行的步骤是，先从索引树中，按时间升序取出前100条，因为索引是排好序的，直接左序遍历即可了

因此，这里mysql并没有做排序动作，如果想降序，则右序遍历索引树，取出100条即可，查询固然快，

那么联合索引的时候，是怎样的呢？

select * from acct_trans_log WHERE acct_id = 3095 order by create_time desc limit 0,10

使用组合索引：idx_acct_id_create_time

这个时候，因为acct_id是联合索引的前缀，因此可以很快实行检索，

如果sql是

select * from acct_trans_log WHERE acct_id = 3095

出来的数据是按如下逻辑排序的

3095+time1

3095+time2

3095+time3

默认是升序的，也就是说，次sql相当于

select * from acct_trans_log WHERE acct_id = 3095 order by create_time

他们是等效的。

如果我们把条件换成order by create_time desc limit 0,10呢

这时候，应该从idx_acct_id_create_time树右边叶子节点倒序遍历，取出前10条即可

因为数据的前缀都是3095，后缀是时间升序。那么我们倒序遍历出的数据，刚好满足order by create_time desc

因此也无需排序。

以上，充分考虑where后面的查找，是否能够匹配上索引，是否符合索引递增的特性

那么语句：

select * from acct_trans_log force index(idx_acct_id_create_time) WHERE acct_id in(3095,1000000000009000757) order by create_time desc limit 0,10

为什么排序无法用索引呢？

我们先分析下索引的排序规则

已知：

id1<id2<id3...
time1<time2<time3....

查询结果集排序如下：

id1+time1

id1+time2

id1+time3

id2+time1

id2+time2

id2+time3

索引出来的默认排序是这样的，id是有序的，时间是无序的，因为有2个id，优先按id排序，时间就是乱的了，

这样排序将会用filesort，这就是慢的原因，也是排序没有用到索引的原因。

即，即使根据索引拿到数据后，还得进行二次排序，才能最终确定结果，使用filesort了。

mysql索引创建规则

索引优缺点:为主键外建where子句建立索引可以加速数据库查询,但是索引占用内存,同时update和insert的时候需要同步修改;索引的实现通常使用其变种B+树。

建立索引方式:create index 索引名 on 表名(列名)；

细节问题:

)如果一张表的数据量很大而符合条件的结果又很少,那么不加索引会引起致命性的结果下降,每次查找一条特定的数据都会进行一次全表扫描
）防止过度索引,比如性别只有两个值,此时对该列建立索引不仅没有什么优势,反而会影响更新插入等操作的速度.
3.)如果where条件进行了联合查询,则可以使用复合索引,如:

Select * from users where area=”beijing” and age=22;此时可以对area和age建立联合主键，而不是单单对area做索引，因为联合索引更加迅速

如果我们创建了(area,age,salary)复合主键,此时其实相当于创建了(area,age,salary),(area,age),(area)三个索引,这被称为最佳左前缀;因此在建立主键的时候应该将最常用的结果并且字段类型比较小的字段放在前面.

索引不会含有null值得列,如果复合索引中只要有一列含有null值,那么这一列在复合索引中就是无效的.
Mysql查询中只使用一个索引,如果where子句中已经使用了索引,那么order by中的列是不会使用索引的.如果排序使用了多个列,可以考虑复合索引
对于like “%a%”不会使用索引,但是类似 like “aa%”可以使用索引

哪些字段适合添加索引：
1、表的主键、外键必须有索引；

2、数据量超过300的表应该有索引；

3、经常与其他表进行连接的表，在连接字段上应该建立索引；

4、经常出现在Where子句中的字段，特别是大表的字段，应该建立索引；

5、索引应该建在选择性高的字段上；

6、索引应该建在小字段上，对于大的文本字段甚至超长字段，不要建索引；

7、复合索引的建立需要进行仔细分析；尽量考虑用单字段索引代替：

A、正确选择复合索引中的主列字段，一般是选择性较好的字段；

B、复合索引的几个字段是否经常同时以AND方式出现在Where子句中？单字段查询是否极少甚至没有？如果是，则可以建立复合索引；否则考虑单字段索引；

C、如果复合索引中包含的字段经常单独出现在Where子句中，则分解为多个单字段索引；

D、如果复合索引所包含的字段超过3个，那么仔细考虑其必要性，考虑减少复合的字段；

E、如果既有单字段索引，又有这几个字段上的复合索引，一般可以删除复合索引；

F、如果(a，b，c)是联合索引，where a='a' and b>'b' and c='c',那么c实际不会走索引。

8、频繁进行数据操作的表，不要建立太多的索引；

9、删除无用的索引，避免对执行计划造成负面影响；

上面说明了联合索引和多个单字段索引分别在什么情况下使用：

复合索引的几个字段是否经常同时以AND方式出现在Where子句中
单字段查询是否极少甚至没有
如果上面两个答案都是‘是’则使用联合索引