五、索引——B+树索引

提示：文章内容来自《mysql是怎样运行的》以及部分B站宋红康老师的视频，这里仅仅是我的笔记，对重点内容的记录。强烈推荐购买这本书《mysql是怎样运行的》。

---

一、如果没有索引

首先说明一下如果没有索引数据是怎么查找的
1、数据量小，一个页就能存储：如果是按主键查找的话，可以在页中使用二分查找，找到对应的槽，再遍历槽中的数据，快速找到指定的数据
如果是按照其他列，因为在数据页中，并没有为非主键建立目录项（这里是分析没有索引的情况），因此就必须
从最小记录开始依次遍历单向表中的每一条记录
2、如果数据量大，在很多页中查找：我们甚至都无法快速定位到数据在哪个页中，因此就得全表扫描，运气好的话，第一个页就是，运气不好的话，得找很久，而且这里会有很多的随机IO发生，全表扫描对数据量大的可想有多慢
示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。

二、以聚簇索引为例子说明B+树索引结构

索引：索引的出现就是为了加速数据查找的速度。

一个B+树的索引的数据结构就是如此
首先对B+树的索引的细节说一下：
1、从下面开始，最下面这层是页子节点，中间是内节点，最上是节点
2、record_type:记录头信息的一项属性，表示记录的信息，其中，0表示普通索引，2表示Infimum，3表示Supremum，1表示目录项的记录
这个目录项是索引结构中的目录项，在上图中对应的是中间那层，也就是内节点，这里不同于页中结构的目录项
3、next_record:当前数据到下一条数据的偏移
4、页与页是双向链表，并且，下一个页的记录的值主键值（聚簇索引）必须大于上一个页
5、中间这层叫做目录项页，是用来快速查叶子节点，存储了页中的最小主键值（聚簇索引）和指向的页号
6、页里面的数据是按照主键递增的单向列表
7、一般说几层就需要几次IO，但是我们后面说根节点其实是常驻内存的，那么我们说的IO次数1-3次主要是因为数据量大的时候，会生成四层的B+索引，一般不会超过四层，因为四层已经能存储很夸张的数据量了

三、索引的分类

3.1 聚簇索引

1） 使用主键值进行记录和页的排序
a、页（包括叶子节点和内节点）内记录的是按主键大小顺序排成的单项列表，页内的记录被分为若干个组，每个组中主键值最大的记录在页内的偏移量会被当作槽一次存放在页目录中，我们可以在页目录中，通过二分查找快速定位到主键列等于某个值的记录
b、各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向列表。
c、存放目录项的页分为不同的层级，在同一层级中的页也是根据页中的目录项记录的主键大小顺序排成双向链表
2） 数据中页的节点存储的是完整的数据记录，所谓完成的记录就是这个记录中存储了所有列的值，包括隐藏列。

3.2 二级索引

加入以某个表的中列c2创建索引
1）、使用记录c2列的大小进行记录和页的排序
a、页内的大小是按照c2的大小顺序排成的单向列表，页内的记录被分为若干个组，每个组中c2的列的最大的记录的偏移量会被当作槽依次放在页目录中，我们可以通过快速查找快速定位c2列等于某个值的记录
b、各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表
c、存放目录项的页分为不同的层级，在同一层级中的页也是根据页中的目录项记录的主键大小顺序排成双向链表
2）、B+树的叶子节点存储的并不完整的用户记录，而是c2列+主键这两个列的值
3）、目录项记录的是“索引列+页号”
（建议看我文章的买本书。。。。再次推荐《mysql是怎样运行的》，后面会对文章内容进行修改和补充，这些图片先凑合用）

回表：我们如果使用c2进行查找完整的数据的时候，需要先在聚簇索引中查找出主键的值，然后拿着主键去聚簇索引中找完整的数据，后面这一个动作就叫做“回表”

3.3 联合索引

我们也可以同时以多个列的大小作为排序规则
1）先把各个记录按照c2列进行排序
再记录的c2列相同的情况下，再按照c3列进行排序
2）每条目录项记录都是由c2列、c3列、页号这三部分组成
3）B+树的叶子节点处的用户记录由c2列、c3列和主键组成

3.4 mysql8.0的新特性

3.4.1 降序索引

8.0之前，B+数的叶子节点或者是非叶子节点，无论是叶子内部的数据，还是页与页之间的关系都是通过索引列从小到大排序的，聚簇索引的话是通过按照主键的大小排序，非聚簇索引的话，如果是单列索引，则按照索引列进行排序，如果是联合索引【列名1、列名2】，首先按照列名1的大小进行排序，只有在列名大小一样时，才按照列名2进行排序；无论那种方式，都是升序的。页与页之间同通过双向链表进行连接，页内的数据是通过单向列表进行连接并且是从小到大，不是说8.0之前不支持降序，只不过由于页内的数据是单列表，不适合反向的降序排序而已，效率会比较低。因此提出了降序排序

我们只需要在创建索引的时候，指定排序方式即可：
CREATE TABLE ts1(a int,b int,index idx_a_b(a,b desc)

3.4.2 隐藏索引

如果是显式的删除索引的话，首先删除索引，因为索引一般都比较大，删除的过程会会占用较多的系统资源，其次，如果我们删除错了的话，还需要再创建回来，得不偿失。
那么为了解决这一问题，数据表在创建的时候或者对已经存在的表，就允许我们使用INVISIBLE指定索引隐藏属性，这样如果不想使用某个索引的话，直接把索引隐藏起来，而不是删除索引，想用的使用，再修改过来就行了，这样就比直接删除索引的成本高很多。
在MySQL 8.x版本中，为索引提供了一种新的测试方式，可以通过查询优化器的一个开关（use_invisible_indexes）来打开某个设置，使隐藏索引对查询优化器可见。如果 use_invisible_indexes设置为off(默认)，优化器会忽略隐藏索引。如果设置为on，即使隐藏索引不可见，优化器在生成执行计划时仍会考虑使用隐藏索引。
注：对隐藏索引的理解不能这样认为:我们可以为某个表创建非常多的隐藏索引，这样未来在使用该索引的时候，我们再打开就好了。这样是不对的，因为索引即数据，它也会占据很多空间，造成空间上的消耗，同时对“增删改”操作，也会增加其时间上的开销。因此必须合理的运用索引，删除长时间或几乎不使用的索引

3.5 B+树索引的注意事项

1、根节点万年不动
实际上B+树的形成过程是：
a.每当为某个表创建一个B+树索引，都会为这个索引创建一个根节点页面，最开始表中没有数据的时候，每个B+树对应的根节点中既没有用户记录，也没有目录项记录
b.随后向表中插入用户记录的时候，先把用户记录存储在这个根节点
c.在根节点可用空间用完时继续插记录，此时会将根节点中所有的记录复制到一个新分配的页a，然后对这个页a进行页分裂，得到一个页b，这时新插入的数据会根据键值的大小分配到页a和页b中，根节点此时便升级为存储目录项的页，也就是需要把页a和页b对应的目录项记录插入到根节点中
在这个过程中需要注意的是，一个B+树索引的根节点自创建之日起便不会在移动（也就是页号不再改变），这样只要我们对某个表建立一个索引，那么他的根节点就会记录到某个地方（数据字典），但凡是InnoDB存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而访问这个索引
2、内节点中目录项记录的唯一性
上面我们讲各种索引的时候，其实没有特别强调这点，其实内节点为了保证记录的唯一性，它的内容由三个部分组成：索引列的值+主键（非空且唯一）+页号
3、一个页面至少容纳2条记录

四 、MyISAM中的索引

首先说明的是MyISAM的索引和数据是分开的，InnoDB有着“索引即数据”一说，可见它其实是不分开的
1、将表中的数据按照插入的顺序单独的存储再一个文件中（称之为数据文件），这个文件并不划分为若干个数据页，有多少个记录就往这个文件中塞多少记录，这样我们就可以通过页号快速的访问到记录
2、MySIAM存储引擎的表会把索引信息单独存储到另一个文件(称之为索引文件)，MySIAM会为表的主键单独创建一个索引，只不过索引的叶子节点中存储的不是完整的用户记录，而是主键与行号的组合，也就是通过索引找到对应的行号，通过行号去找对应的记录
这点和InnoDB是不一样的，InnoDB只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而MyISAM需要进行一次回表操作，这也意味着MyISAM建立的索引相当于全部是二级索引
3、如果有必要也可以建立来联合索引，这点和InnoDB相似，但是同样在叶子节点记录的是相应的列+行号

注意：MyISAM的“回表”其实是比较快的，直接拿偏移地址去文件中取数据，和InnoDB的“回表”不一样， InnoDB索引即数据，数据即索引，MyISAM数据就是数据，索引就是索引 ，MyISAM可以没有主键。

五 、其他索引结构

5.1 Hash索引

5.2 为什么innoDB不用hash索引？

Hash结构效率高，那为什么索引结构要设计成树型呢？
首先说明一下，MyISAM和InnoDB是不支持hash索引的，Memory支持hash索引，不过InnoDB存在hash自适应，就是把访问频率高的数据放在一个hash表中

Hash虽然根块，时间复杂度为o（1），但是hash适合与等值查询，不适合范围查询
比如使用=或in的话，hash很快，但是对于 > < 或者排序的话，hash就不合适了

5.3 B树索引

首先看一下B树的结构：

1. 有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数
   +1。
   索引 / 存储引擎 MyISAM InnoDB Memory
   R-Tree索引 支持 支持 不支持
2. 非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最
   小）。
3. 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中， 非
   叶子节点既保存索引，也保存数据记录 。
4. 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大
   小从小到大顺序链接。
   B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树。
   但B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然

5.5 innoDB为什么不用B树？

单个页默认是存储16kb的数据，对于内节点来说或者非聚簇索引，B+树不需要存储全部数据，也就说同大小的页，B+数能够检索更多的数据，树结构更矮胖，IO次数越少，同时B树由于要存储完整的数据，那么在多个索引中，会存在大量的数据冗余。