MySQL 索引和 B+tree 结构
目录
0.关于索引的常见面试题
1.什么是索引?
索引的优缺点
2.索引的数据结构,为什么InnoDb引擎使用B+tree作为索引的数据结构?
分析怎样的索引才是好的
二插搜索树
红黑树
B-Tree
B+Tree
哈希
为什么 InnoDB 存储引擎选择使用 B+tree 索引结构?
3.B+tree结构的数据个数和树高的计算
4.索引的分类
5.有关索引的语法
6.索引的使用
7.索引失效的情况
8.MySQL中自动或人为优化索引的方法
覆盖索引优化
前缀索引优化
索引下推优化
0.关于索引的常见面试题
- 什么是索引?
- 索引底层使用了什么数据结构和算法?
- 为什么 MySQL InnoDB 选择 B+tree 作为索引的数据结构?
- 什么情况下索引会失效?
- 有什么优化索引的方法?
- .....
1.什么是索引?
一句话简单来说,索引的出现就是为了提高数据查询的效率,就像书的目录一样。一本 1000 页的书,如果你想快速找到其中的某一个知识点,在不借助目录的情况下,那你可能得找一会儿。同样,对于数据库的表而言,索引其实就是它的“目录”。
所以,索引就是提高查询速度的数据结构(有序的)。而能提高查询速度的,说明这些数据是按照一定规则排序好的。
索引的优缺点
优点:
- 提高数据检索效率,降低数据库的IO成本
- 通过索引列对数据进行排序,降低数据排序的成本,降低CPU的消耗
缺点:
- 索引列也是要占用空间的
- 索引大大提高了查询效率,但降低了更新的速度,比如 INSERT、UPDATE、DELETE(插入等这些操作需要把数据进行排序)
在 MySQL 中,索引是在存储引擎层实现的,所以并没有统一的索引标准,即不同存储引擎的索引的工作方式并不一样。
2.索引的数据结构,为什么InnoDb引擎使用B+tree作为索引的数据结构?
前面说了索引是数据结构,那数据结构是有多种的。为什么在大多数情况下,B+tree打败了其他数据结构呢?
分析怎样的索引才是好的
数据库的索引是保存到磁盘上的,因此当我们通过索引查找某行数据的时候,就需要先从磁盘读取索引到内存,再通过索引从磁盘中找到某行数据,然后读入到内存,也就是说查询过程中会发生多次磁盘 I/O,而磁盘 I/O 次数越多,所消耗的时间也就越大。
所以,我们希望索引的数据结构能在尽可能少的磁盘的 I/O 操作中完成查询工作,因为磁盘 I/O 操作越少,所消耗的时间也就越小。
另外,MySQL 是支持范围查找的。
所以,要设计一个适合 MySQL 索引的数据结构,至少满足以下要求:
- 能在尽可能少的磁盘的 I/O 操作中完成查询工作;
- 要能高效地查询某一个记录,也要能高效地执行范围查找(即索引最好是按照顺序排序的);
不熟悉MySQL的同学想到数据结构,可能会想到数组,链表这些。这些是不适合在MySQL查询使用的。因为其查询效率低,时间复杂度是O(n)。而且使用数组插入又想要排序好的话,时间复杂度也是O(n)。
要想插入和查询性能都比较好的话,那可以想到二叉树,而有序排序的话,那就是二叉查找树。
二插搜索树
- 顺序插入时候会形成一个单项链表,查询性能大大降低
- 而在大数据量情况下,会导致层级较深,检索速度慢 (一层就是一次磁盘 I/O 操作)
所以放弃二叉搜索树。
红黑树
红黑树是自平衡搜索树,是二插搜索树的其中一种类型。
- 解决二叉树的顺序插入后,树不平衡的问题(但插入性能比二插搜索树差点)
- 在大数据量的情况下,层级还是较深,检索速度较慢
B-Tree
现在就是要解决层次深的问题,很明显是每个节点只有两个子节点造成的,要是一个节点下有多个子节点,那层次就可以控制在合理范围了。可以用到B-Tree(多路平衡查找树) 。
这里,以一棵最大度数(max-degree,指一个节点的子节点个数)为5(5阶)的 b-tree 为例(每个节点最多存储4个key,5个指针)。
需要注意: B 树的每个节点都包含数据(索引+记录)
这里可以稍微解决红黑树层次深的问题,但还是不够好。数据都是以页为单位存放的, MySQL中一页是16k,而在B树中,非叶子节点和叶子结点都会存放数据,一页中可以放的指针和数据太少。当数据量也很大的时候,即层次可能还是比较深,IO次数变多。
那可以想到只有叶子节点存放数据,而其他节点没有存放数据的,那一页中就可以保存更多的索引值了,那就可以使用到B+tree。
B+Tree
图片中橙色的是页/块,存储索引和数据。
上图是MySQL优化后的B+ Tree,和原始的相比是在叶子节点添加了双向循环链表的。
和B-tree相比:
- 所有的数据都会出现在叶子节点。
- 叶子节点形成一个双向循环链表。
- 非叶子节点仅仅起到索引数据作用,具体的数据都是在叶子节点存放的。
这样每页的索引可以放更多了,那树高自然就可以矮了嘛,磁盘的随机 I/O 读取次数相对就减少了。而且叶子结点之间用链表有序连接,所以扫描全部数据只需扫描一遍叶子结点,利于扫库和范围查询。
哈希
哈希索引就是采用一定的hash算法,将键值换算成新的hash值,映射到对应的槽位上,然后存储在hash表中。
如果两个(或多个)键值,映射到一个相同的槽位上,他们就产生了hash冲突(也称为hash碰撞),可以通过链表来解决。
其特点:
- 只能用于等值查询较(=,in),不支持范围查询(between,>,< ,…)
- 无法利用索引完成排序操作
- 查询效率高,通常(不存在hash冲突的情况)只需要一次检索就可以了,效率通常要高于B+tree索引
所以,哈希表这种结构适用于只有等值查询的场景,比如 Memcached 及其他一些 NoSQL 引擎。
为什么 InnoDB 存储引擎选择使用 B+tree 索引结构?
对比二叉搜索树和自平衡二叉树(以红黑树举例)
- 层级更少,搜索效率高。
对比B-tree
- B+ 树叶子结点之间用链表有序连接,所以扫描全部数据只需扫描一遍叶子结点,利于扫库和范围查询;B 树由于非叶子结点也存数据,所以只能通过中序遍历按序来扫。即是对于范围查询和有序遍历而言,B+ 树的效率更高。
- B+ 树更相比 B 树减少了 I/O 读写的次数。B+ 树的非叶子结点只存关键字不存数据,因而单个页可以存储更多的关键字,即一次性读入内存的需要查找的关键字也就越多,磁盘的随机 I/O 读取次数相对就减少了。
- B+树的查询效率更加稳定,任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。
对比Hash索引
- B+tree支持范围匹配及排序操作
3.B+tree结构的数据个数和树高的计算
假设一行数据大小为1k,一页(一页大小是16k)中可以存储16行这样的数据。InnoDB 的指针占用6个字节的空间,主键假设为bigint,占用字节数为8。
可得公式:n * 8 + (n + 1) * 6 = 16 * 1024,其中 8 表示 bigint 占用的字节数,n 表示当前节点存储的key的数量,(n + 1) 表示指针数量(比key多一个)。算出n约为1170。
如果树的高度为2,那么他能存储的数据量大概为:1171 * 16 = 18736;
如果树的高度为3,那么他能存储的数据量大概为:1171 * 1171 * 16 = 21939856。
4.索引的分类
聚集索引选取规则:
- 如果存在主键,主键索引就是聚集索引
- 如果不存在主键,将使用第一个唯一(UNIQUE)索引作为聚集索引
- 如果表没有主键或没有合适的唯一索引,则 InnoDB 会自动生成一个 rowid 作为隐藏的聚集索引
5.有关索引的语法
--创建索引,如果不加索引类型参数,则创建的是常规索引
CREATE [ UNIQUE | FULLTEXT ] INDEX index_name ON table_name (index_col_name, ...);
--查看索引
SHOW INDEX FROM 表名;
--删除索引
DROP INDEX index_name ON 表名;
例子:
mysql> desc test;
+-------+-------------+------+-----+---------+-------+
| Field | Type | Null | Key | Default | Extra |
+-------+-------------+------+-----+---------+-------+
| id | int | NO | PRI | NULL | |
| name | varchar(10) | YES | | NULL | |
| age | int | NO | | NULL | |
+-------+-------------+------+-----+---------+-------+
3 rows in set (0.00 sec)
mysql> create index idx_age on test(age);
Query OK, 0 rows affected (0.05 sec)
Records: 0 Duplicates: 0 Warnings: 0
mysql> show create table test;
+-------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table | Create Table |
+-------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| test | CREATE TABLE `test` (
`id` int NOT NULL,
`name` varchar(10) DEFAULT NULL,
`age` int NOT NULL,
PRIMARY KEY (`id`),
KEY `idx_age` (`age`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci |
+-------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)
mysql> show index from test;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| test | 0 | PRIMARY | 1 | id | A | 7 | NULL | NULL | | BTREE | | | YES | NULL |
| test | 1 | idx_age | 1 | age | A | 1 | NULL | NULL | | BTREE | | | YES | NULL |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
2 rows in set (0.01 sec)
mysql> drop index idx_age on test;
Query OK, 0 rows affected (0.02 sec)
Records: 0 Duplicates: 0 Warnings: 0
mysql> show index from test;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| test | 0 | PRIMARY | 1 | id | A | 7 | NULL | NULL | | BTREE | | | YES | NULL |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
1 row in set (0.01 sec)
6.索引失效的情况
内容也比较多,总结在该文章中
MySQL索引失效与MySQL8新添加的索引特性
7.MySQL中自动或人为优化索引的方法
覆盖索引优化
说到覆盖索引优化,那就要先讲回表查询。上图中的id是主键,name也创建了二级索引。但是上图的sql语句就需要在name二级索引中找到Arm,之后回到id索引再查找所有数据,这个就是回表查询。
那如果查询语句是select id from user where name='Arm';这个只查找id不用回表查询,因为name索引树上是已有id值了。(二级索引树上数据都是主键值的)
也就是说,在这个查询里面,索引 name已经“覆盖了”我们的查询需求,我们称为覆盖索引。
由于覆盖索引可以减少树的搜索次数,显著提升查询性能,所以使用覆盖索引是一个常用的性能优化手段。
这个就需要人为地修改sql语句,尽量符合覆盖索引要求。
前缀索引
前缀索引顾名思义就是使用某个字段中字符串的前几个字符建立索引,那我们为什么需要使用前缀来建立索引呢?
使用前缀索引是为了减小索引字段大小,可以增加一个索引页中存储的索引值,有效提高索引的查询速度。在一些大字符串的字段作为索引时,使用前缀索引可以帮助我们减小索引项的大小。
但是,其也有缺点,使用前缀索引可能会增加扫描行数,这会影响到性能。还有对覆盖索引的影响。
来看个场景:有个表user,其中id是主键,name字段类型是varchar(20)。现在给字段name添加普通索引index1(name)或者 前缀索引index2(name(7))。
语句1
select id,username from user where username='zhangsan';
语句2
select id,name,phone from user where name='zhangsan';
语句2就多查了个phone字段。
所以,如果使用 index1(即 name整个字符串的索引结构)的话,可以利用覆盖索引,从 index1 查到结果后直接就返回了,不需要回到 ID 索引再去查一次。
而如果使用 index2(即 name(7) 索引结构)的话,就不得不回到 ID 索引再去判断 email 字段的值。
即使你将 index2 的定义修改为 name(20) 的前缀索引,这时候虽然 index2 已经包含了所有的信息,但 InnoDB 还是要回到 id 索引再查一下,因为系统并不确定前缀索引的定义是否截断了完整信息。
即是,使用前缀索引就使用不上覆盖索引对查询性能的优化,这也是选择是否使用前缀索引时需要考虑的一个因素。
索引下推优化
在查询select * from user idcard liek '123%' and age=10;表user创建了联合索引(idcard,username,age)。
所以这个语句在搜索索引树的时候,只能用 “123”,找到第一个满足条件的记录 ID1。当然,这还不错,总比全表扫描要好。
然后呢?当然是判断其他条件是否满足。
在 MySQL 5.6 之前,只能从 ID1 开始一个个回表。到主键索引上找出数据行,再对比字段值。
而 MySQL 5.6 引入的索引下推优化(index condition pushdown), 可以在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数。
推荐阅读
-
这篇 MySQL 索引和 B+Tree 文章通俗易懂!-创建索引的几个原则
-
MySQL 和 Hive 存储引擎在表、索引数量上有哪些限制?-MySQL 存储引擎的限制
-
使用 frm 文件和 ibd 文件恢复 MySQL 表结构和表数据
-
什么是数据库事物?为什么需要数据库事物,事物有哪些特征?事物的隔离级别是什么?-1.什么是数据库事务? 1.事务是作为一个逻辑单元执行的一系列操作。一个逻辑工作单元必须具备四个属性,即ACID(原子性、一致性、隔离性和持久性)属性,只有这样才能成为事务: 原子性 2.事务必须是一个原子工作单元;它的数据修改要么全部执行,要么全部不执行。 一致性 3.事务完成时,所有数据必须保持一致。在相关数据库中,所有规则都必须适用于事务的修改,以保持所有数据的完整性。事务结束时,所有内部数据结构(如 B 树索引或双向链接表)必须正确无误。 隔离 4.并发事务的修改必须与其他并发事务的修改隔离。一个事务会在另一个并发事务修改之前或之后查看某一状态下的数据,而不会查看中间状态下的数据。这就是所谓的可序列化,因为它允许重新加载起始数据和重放一系列事务,从而使数据最终处于与原始事务执行时相同的状态。 持久性 5.事务完成后,它对系统的影响是永久性的。即使在系统发生故障的情况下,修改也会保留。 2. 为什么需要数据库事物,事物有哪些特征? 事物对数据库的作用是对数据进行一系列操作,要么全部成功,要么全部失败,防止出现中间状态,确保数据库中的数据始终处于正确、和谐的状态。 特征:原子性、一致性、隔离性、持久性,以及其他特征 原子性(Atomicity):所有操作在事务开始后,要么全部做完,要么全部不做,不可能停滞在中间环节。事务执行过程中出现错误时,会回滚到事务开始前的状态,所有操作就像没有发生一样。也就是说,事务是一个不可分割的整体,就像化学中的原子一样,是物质的基本单位。 一致性(Consistency):在事务开始之前和结束之后,数据库的完整性约束都没有被破坏。例如,如果 A 转钱给 B,A 不可能扣除这笔钱,但 B 却没有收到这笔钱。 隔离:在同一时间内,只允许一个事务请求相同的数据,不同事务之间没有干扰。例如,甲正在从一张银行卡上取款,在甲取款过程结束之前,乙不能向这张卡转账。 持久性(耐用性):事务完成后,事务对数据库的所有更新都将保存到数据库中,无法回滚 3.事务的隔离级别有哪些? 数据库事务有四种隔离级别,从低到高分别是未提交读取(Read uncommitted)、已提交读取(Read committed)、可重复读取(Repeatable read)、可序列化(Serializable)。此外,事务的并发操作中可能会出现脏读、不可重复读、幽灵读等情况。事务并发问题 脏读:事务 A 读取事务 B 更新的数据,然后事务 B 回滚操作,那么事务 A 读取的数据就是脏数据。 不可重复读取:事务 A 多次读取同一数据,事务 B 在事务 A 多次读取期间更新并提交数据,导致事务 A 多次读取同一数据时结果不一致。 幻影读取:系统管理员 A 将数据库中所有学生的具体分数改为 ABCDE 等级,但系统管理员 B 在此时插入了具体分数的记录,当系统管理员 A 更改结束后发现仍有一条记录未被更改,仿佛发生了幻觉,这称为幻影读取。 小结:不可重复读和幻读容易混淆,不可重复读侧重于修改,幻读侧重于增删。解决不可重复读问题只需锁定满足条件的行,解决幻读问题则需要锁定表 MySQL 事务隔离级别
-
设计和实施基于 vue 的 MOBA 类游戏策略共享平台 | Springboot + Vue + Mysql + Java + B/S 结构(可运行源代码 + 数据库 + 设计文档)
-
MySQL EXPLAIN 和从 LIKE、REGEXP 向下推送索引示例
-
Python 与 MySQL 的连接 - III.表结构和代码实现
-
个人健身和教练预约管理系统的设计与实施 | SpringBoot + Mysql + Java + B / S 结构(可运行源代码 + 数据库 + 设计文档)
-
[MySQL]MySQL索引和B+树的概念
-
mysql 数据库头像字段_Mysql 查询数据库表结构和字段类型及显示方式