参考资料：[掘金] MySQL 是怎样运行的：从根儿上理解 MySQL
(https://juejin.cn/book/6844733769996304392/section)
第七章- 快速查询的秘籍 —— B+ 树索引
第八章- 好东西也得先学会怎么用 —— B+ 树索引的使用
数据页
数据页-普通用户记录
- InnoDB 使用页来作为管理存储空间的基本单位，每个页拥有16KB的连续存储空间。
- 每个普通用户记录数据页中的记录会按主键值从小到大的顺序组成一个单向链表。
- 页目录：
- 页目录是一个线性表，将数据记录进行分组，记录每组数据第一个元素的地址。（于最小记录所在的分组只能有 1条记录，最大记录所在的分组拥有的记录条数只能在 1~8 条之间，剩下的分组中记录的条数范围只能在是 4~8 条之间）
- 单个数据页查找指定主键方法：a）通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录。b）通过记录的
next_record属性遍历该槽所在的组中的各个记录。
单页的数据结构示意图：
image.png
数据页-目录项记录
- 各个普通用户记录数据页可以组成一个双向链表，也是按照key的大小顺序排列的。即：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。
- 目录项页中保存了普通用户记录页的最小值和页面地址。
- 多个数据页查找指定主键的方法：如查找主键为
20的记录。a) 先到存储目录项记录的页，也就是页30中通过二分法快速定位到对应目录项，因为12 < 20 < 209，所以定位到对应的记录所在的页就是页9。b) 再到存储用户记录的页9中根据二分法快速定位到主键值为20的用户记录。
image.png
InnoDB中索引（B+树）
- 如果有多个目录项页，为这些存储
目录项记录的页再生成一个更高级的目录。就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据。这就是B+树的结构。 - 下图是3层的B+树，一般我们用到B+树都不会超过4层，否则数据量太大会影响查询和修改效率（考虑分区、分库分表）。
B+树示意图：
image.png
B+树的特点：
- 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
- 页内的记录是按照主键的大小顺序排成一个单向链表。
- 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
- 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
-
B+树只有叶子节点储存了value值，非叶子节点只储存key值和页面地址。查询的时候，必须经历从根节点到叶子节点一层一层往下搜索。
聚簇索引
- 聚簇索引中，
B+树的叶子节点存储的是完整的用户记录。所谓完整的用户记录，就是指这个记录中存储了所有列的值。 -
InnoDB存储引擎会自动的为我们创建聚簇索引，索引的key值为主键值（primary key）。
二级索引
使用c2列创建二级索引：
-
B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。 - 目录项记录中不再是
主键+页号的搭配，而变成了c2列+页号的搭配。
利用二级索引搜索用户记录的过程（需要回表）：
-
利用c2索引的B+树，查找用户记录的主键。
-
根据
c2列的值到聚簇索引中再查一遍，获取完整的用户记录，这个过程叫回表。（如果只查询c2列和主键，则不需要回表。因此select语句应只查询必要字段，避免select *。）
image.png
联合索引
我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按照c2和c3列的大小进行排序，这个包含两层含义：
- 先把各个记录和页按照
c2列进行排序。 - 在记录的
c2列相同的情况下，采用c3列进行排序
为c2和c3列建立的索引的示意图如下：
image.png
如图所示，我们需要注意一下几点：
- 每条
目录项记录都由c2、c3、页号这三个部分组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序。 -
B+树叶子节点处的用户记录由c2、c3和主键c1列组成。
唯一索引和普通索引
-
唯一索引：
ALTER TABLE `tt_test` ADD UNIQUE INDEX `un_index_title` (`title`) USING BTREE ; -
普通索引
ALTER TABLE `tt_test` ADD INDEX `k_title` (`title`) USING BTREE ;
普通索引的B+树
-
使用上文描述B+树存在的问题：
索引列 + 页号无法确定唯一的用户数据，在新插入记录时，无法确定数据放在叶子节点的哪个页面。 -
我们需要保证在B+树的同一层内节点的目录项记录除
页号这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的：- 索引列的值
- 主键值
- 页号
MyISAM中的索引方案
- MyISAM 中的记录按照记录的插入顺序单独存储在一个文件中，包含行号和用户数据。
-
MyISAM会单独为表的主键创建一个索引，索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 行号的组合。 - 根据主键查询时，需要先通过索引找到对应的行号，再通过行号去找对应的记录，也就是需要回表。（MyISAM索引叶子节点记录的是物理地址偏移量，回表比InnoDB快）
索引的代价
一个表上索引建的越多，就会占用越多的存储空间，在增删改记录的时候性能就越差。
-
空间上的代价
这个是显而易见的，每建立一个索引都要为它建立一棵
B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会占用16KB的存储空间，一棵很大的B+树由许多数据页组成，那可是很大的一片存储空间呢。 -
时间上的代价
每次对表中的数据进行增、删、改操作时，都需要去修改各个
B+树索引。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收啥的操作来维护好节点和记录的排序。
B+树索引适用的条件
-
全值匹配
搜索条件中的列和索引列完全一致
-
匹配左边的列
联合索引左边的列，必须是左连续的列。
例如：联合索引
idx_name_birthday_phone_number中列的定义顺序是name、birthday、phone_number。以下语句适用于索引查询
SELECT * FROM person_info WHERE name = 'Ashburn'; SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27'; -
匹配列前缀
适用于字符串查询。字符串排序实际上是：先按照字符串的第一个字符进行排序，如果第一个字符相同再按照第二个字符进行排序，以此类推。
像这样的前缀查询语句可以适用于索引查询：
SELECT * FROM person_info WHERE name LIKE 'As%'; -
匹配范围值
SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';范围查找的过程如下：
- 通过B+树在叶子节点中找到第一条
name值大于Asa的二级索引记录，读取该记录的主键值进行回表操作，获得对应的聚簇索引记录后发送给客户端。 - 根据上一步找到的记录，沿着记录所在的链表向后查找（同一页面中的记录使用单向链表连接起来，数据页之间用双向链表连接起来）下一条二级索引记录，判断该记录是否符合name < 'Barlow'条件，如果符合，则进行回表操作后发送至客户端。
- 重复上一步骤，直到某条二级索引记录不符合name <'Barlow'条件为止。
- 通过B+树在叶子节点中找到第一条
-
精确匹配某一列并范围匹配另一列
SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday > '1980-01-01' AND birthday < '2000-12-31'查找过程如下：
-
name = 'Ashburn'，对name列进行精确查找，当然可以使用B+树索引了。 -
birthday > '1980-01-01' AND birthday < '2000-12-31'，由于name列是精确查找，所以通过name = 'Ashburn'条件查找后得到的结果的name值都是相同的，它们会再按照birthday的值进行排序。所以此时对birthday列进行范围查找是可以用到B+树索引的。
-
-
用于排序
文件排序（英文名：
filesort） ：一般情况下，我们只能把记录都加载到内存中，利用排序算法排序，如果内存容量不够，还需要借助磁盘空间。文件排序的效率非常低。利用索引排序：（全值匹配或者匹配左边的列）
SELECT * FROM person_info ORDER BY name, birthday, phone_number LIMIT 10;直接提取联合索引
idx_name_birthday_phone_number的前10条记录，再进行回表。注意，以下情况不会用到索引：
-
排序列包含非同一个索引的列。如name和country不是同一个索引中的列。
SELECT * FROM person_info ORDER BY name, country LIMIT 10; -
排序类使用了复杂的表达式，如使用了UPPER函数
SELECT * FROM person_info ORDER BY UPPER(name) LIMIT 10; -
ASC、DESC混用
-
-
用于分组
和用于排序类似，分组列的顺序也需要和索引列的顺序一致，也可以只使用索引列中左边的列进行分组。
SELECT name, birthday, phone_number, COUNT(*) FROM person_info GROUP BY name, birthday, phone_number
回表的代价
-
回表会使用到两个
B+树索引，一个二级索引，一个聚簇索引。 -
访问二级索引使用
顺序I/O，访问聚簇索引使用随机I/O。 -
需要回表的记录越多，使用二级索引的性能就越低，甚至让某些查询宁愿使用全表扫描也不使用
二级索引。比方说
name值在Asa～Barlow之间的用户记录数量占全部记录数量90%以上，那么如果使用idx_name_birthday_phone_number索引的话，有90%多的id值需要回表，还不如直接去扫描聚簇索引（也就是全表扫描）。SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow'; -
覆盖索引不需要回表。因此查询的时候尽量只查必要的字段。
由于索引中包含 name, birthday, phone_number 三个字段，以下SQL查询不需要回表操作。
SELECT name, birthday, phone_number FROM person_info WHERE name > 'Asa' AND name < 'Barlow' SELECT name, birthday, phone_number FROM person_info ORDER BY name, birthday, phone_number;
索引注意事项
在使用索引时需要注意下边这些事项：
-
只为用于搜索、排序或分组的列创建索引
只为出现在
WHERE子句中的列、连接子句中的连接列，或者出现在ORDER BY或GROUP BY子句中的列创建索引。 -
为列的基数大的列创建索引
-
列的基数指的是某一列中不重复数据的个数，比方说某个列包含值2, 5, 8, 2, 5, 8, 2, 5, 8，虽然有9条记录，但该列的基数却是3。也就是说，在记录行数一定的情况下，列的基数越大，该列中的值越分散，列的基数越小，该列中的值越集中。 - 最好为那些列的基数大的列建立索引，为基数太小列的建立索引效果可能不好。（如果列的基数小，查出来相同的数据较多，回表的代价也较大）
-
-
索引列的类型尽量小
如能使用int就不使用bigint
- 数据类型越小，在查询时进行的比较操作越快（这是CPU层次的东东）
- 数据类型越小，索引占用的存储空间就越少，在一个数据页内就可以放下更多的记录，从而减少磁盘
I/O带来的性能损耗，也就意味着可以把更多的数据页缓存在内存中，从而加快读写效率。
-
可以只对字符串值的前缀建立索引
前缀索引：只对字符串的前几个字符进行索引也就是说在二级索引的记录中只保留字符串前几个字符。
建立前缀索引的理由：和上一条索引列类型尽量小的理由类似：
-
B+树索引中的记录需要把该列的完整字符串存储起来，而且字符串越长，在索引中占用的存储空间越大。 - 如果
B+树索引中索引列存储的字符串很长，那在做字符串比较时会占用更多的时间。
注意：前缀索引不支持排序，如下
CREATE TABLE person_info( name VARCHAR(100) NOT NULL, birthday DATE NOT NULL, phone_number CHAR(11) NOT NULL, country varchar(100) NOT NULL, KEY idx_name_birthday_phone_number (name(10), birthday, phone_number) ); SELECT * FROM person_info ORDER BY name LIMIT 10; -
-
只有索引列在比较表达式中单独出现才可以适用索引
第一种写法会让索引失效，因为 my_col * 2 不是单独的列，而是包含表达式。
WHERE my_col * 2 < 4 WHERE my_col < 4/2 -
为了尽可能少的让
聚簇索引发生页面分裂和记录移位的情况，建议让主键拥有AUTO_INCREMENT属性。为了避免插入的时候页分裂等操作，让主键拥有AUTO_INCREMENT属性，可以按顺序插入值。
-
定位并删除表中的重复和冗余索引
如下列代码中，idx_name 是冗余索引，因为联合索引 idx_name_birthday_phone_number 已经具备按照name查询的个功能。
CREATE TABLE person_info( id INT UNSIGNED NOT NULL AUTO_INCREMENT, name VARCHAR(100) NOT NULL, birthday DATE NOT NULL, phone_number CHAR(11) NOT NULL, country varchar(100) NOT NULL, PRIMARY KEY (id), KEY idx_name_birthday_phone_number (name(10), birthday, phone_number), KEY idx_name (name(10)) ); -
尽量使用
覆盖索引进行查询，避免回表带来的性能损耗。
B树和B+树对比
参考文章1：https://zhuanlan.zhihu.com/p/27700617
参考文章2：https://www.jianshu.com/p/a15bd7e5252b
image.png
B树和B+树的规则有什么不同：
- B+树的非叶子节点不保存key对应的value值，只有叶子节点保存了value。所有value必须要到叶子节点才能获取到。B树叶子节点和非叶子节点都保存了key和value。
- B+树叶子节点之间组成一个双向链表，B树的叶子节点是单独的。
为什么MySQL选用B+树，B+树相较B树有哪些优点：
- B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
- B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
- B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
- B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。
网友评论