[MySQL]MySQL索引和B+树的概念
MySQL索引与B+树的概念
要说到在数据库相关的知识中,最吸引人的是什么,估计 80% 以上的人都会脱口而出 索引 这个词。我们都知道,这玩意真的好用,非常方便,而且往往优化 MySQL 的第一步就是去建立索引。那么今天,我们就开始学习了解索引这一块的内容,首先当然还是与索引相关的概念。
索引
索引是什么意思?太多教程太多书都会讲到,最典型的例子,去图书馆找书。我们要在一个大型的图书管找一本书,怎么找呢?我们可以先问图书馆的工作人员,比如说找一本 MySQL 相关的书籍。他会告诉你在 电脑科技 相关的书架附近,然后你走到电脑科技区域,会发现有好几排书架,不过每个书架上又会写着 编程、操作系统、网络、办公软件、数据库 等标签。当然,有的书店不一定会把数据库这个分类单独放到一排书架上,所以你也可以到编程相关的书架下面去找。
好了,找到大范围的书架后,你就可以在书架前一本一本的看书名,最后找到你想要的书。
假设,我们假设一种情况,你去的是一个刚开业的书店,书籍还没有经过整理分类,这时候要找一本书,你就得一本一本地看过去。有什么想法?没错,这就是线性查找 O(n) 的时间复杂度。而像上面一样有分类区域,也有分类书架呢?至少是折半,甚至是 Log 级别,效率是不是一下就快了很多。
在数据库中,其实情况也是和上面类似的。一张没有任何索引的表中的数据,就像是胡乱摆放的书库,要找到一条数据你就需要一条一条的查找。数据少的时候问题不大,毕竟计算机的性能已经很强悍了,但是几百上千万甚至是上几十亿的数据,即使是最高配的计算机,也会逐渐产生性能瓶颈。而索引,就是根据指定的索引字段,建立相关的书架分类,让程序根据索引规则能够快速地查找到需要的数据。
生活中其实索引非常常见,我们说了书店,其实每本书的目录,你写的论文目录,公司的员工花名册,组织架构等等,都可以看作是索引。概念好理解,那么索引究竟是如何让我们的查找变快的呢?这就要说到它的数据结构了。
B+树
但凡提到索引,必提 B+树 。之前我们在学习数据结构的时候,讲过树、二叉树,也提到过 B+树 ,但真正要讲这个东西,还是要放到 MySQL ,也就是数据库相关的知识中进行学习。B+树是由B树演化而来,而B树又是AVL平衡二叉树(二叉查找树)优化而来的。一切都源于我们之前学习过的数据结构与算法。
首先我们要明确的是概念是 页 这个关键词。对于索引的存储来说,都是存储在 页 这个结构中,它有页头,也有数据单元,但是,需要注意的一点是,在 InnoDB 这个存储格式中,只有主键索引最底层的页中会存储真实的数据信息。其它层次以及其它索引结构,最终存储的只是主键。因此,使用普通索引查到的其实是主键,然后根据主键再去查找真实的主键索引中的数据。这个操作叫做 回表 。这个概念我们在之后讲覆盖索引的时候还会说到。
除了页之外,在页的上层还有段和簇(区)的概念,它们是页的上级节点。段的空间是无限的,底下是N多个簇,而一个簇里面有 64 个页。页在逻辑上和物理上都是连续的。再向上就是表空间以及物理文件,这些都不在我们的讨论范围内,有兴趣的同学可以自行查找相关的学习资料。
而在 MyISAM 存储格式中,主键索引和普通索引记录的都是数据位置,它的索引是和数据完全分开的,因此,任何索引都有回表操作。
索引页的格式就像下面的图一样。
我们有一个根节点,下面还有一层目录节点,一般来说目录节点会按顺序记录id范围,这个页在数据少的时候也是存放数据的,但是当数据填充满了之后,就会进行页分裂,将数据转而存储到下层页节点上,而当前页成为目录页也叫非数据页。这个目录页就变成了纯指针页,它只存放指向数据页的指针。在填充更多数据之后,就会出现新的一层。在最底层的是数据页,数据页一般存储 16k 的数据,按数据量来看一般最少2条数据。每个页都和父子页以及兄弟页存在关联,其实内部就是链式存储的树结构。
当我们要查找一条数据时,比如我们查找 id 为 222 的数据,首先就是二分法快速定位到目录页,然后目录页中再二分法快速定位到数据页,最后在数据页中遍历获得真实的数据。索引查找到的是页,而不是具体的数据行,数据行是在页中遍历得来的。因此,索引查找的时间复杂度是 O(logn) + 页的 O(n),只不过一个页只有 16k 的数据,所以页中的遍历查找非常快。而对于磁盘IO来说,两层的 B+ 树只需要两次IO。一般来说,三层的主键索引(聚集索引)在假设单行数据为 1k 的情况下,大概能存放 2000w 行左右的数据。所以一般 B+ 树的索引在2-3层的高度是比较常见的,最多四层也能容纳将近几十上百亿的数据量了。
关于页如何分裂,以及如何增加高度分层,原理就更为复杂了,但大体上的概念只要学过树相关概念的同学应该还是能够想明白的。主要就是类似于平衡二叉树的分裂,当元素达到页中元素上限时,将中间数据向上分裂。比如上限五个元素的五叉树,则: A、B、C、D、F,当有元素 E 插入时,会将 C 分裂到上层,形成 C 单独一层,通过 C 的指针指向下一层的 A、B、D、F 这样,并将 E 插入到 F 之前,D 之后,比 C 小的放在左子树,比 C 大的放在右子树。查找 B 元素时,根据 C 判断比 C 小,于是走左侧节点,找到 B 元素。大概原理是这样,但这一块已经大大超出我的能力范围了,所以有兴趣的同学可以自行查找更深入的资料哦。
上述内容就是一个主键索引的 B+树实现。注意,顺序很重要,不管是数字类型的索引还是字符串类型的索引,都会在 B+树 中进行排序,这个概念会影响到之后的 WHERE 条件优化以及 ORDER BY 相关的内容。毕竟它的查找是基于二分查找,而二分最重要的条件就是有序。之所以在某些情况下,ORDER BY 的速度也非常快,正是因为索引早就已经将数据排好了序。
普通索引的结构其实也是类似的,但是底层最后存储的不是真实数据,而是主键ID,这个我们就不单独说了,在这里我们再重点看的就是联合索引,也就是多个字段的索引是怎么建树的。
假设我们给 a、b、c 三个字段建立联合索引,那么它会一层一层的建立索引,也就是说,a 下面包含 b ,b 下面包含 c ,最后形成多键值组合排列的页节点。其实这也就是在数据库中最经常讲到的写 WHERE 语句要遵循 最左匹配 原则的原因。如果我们的查询条件能够按照顺序以 a->b->c 的形式查找,那么索引的利用率也可以达到最大,效率也是最好的。这种页节点很明显会占用更多的空间,因此,联合索引的 B+ 树的高度可能会比聚集索引要更高一些。
普通索引和联合索引最底层的数据页存储的都是主键id指针,同时在目录以及上层页也有存储这些字段自己的值,因此,如何只是查询索引相关的字段,就可以避免回表,比如 select a,b,c from t where a=1 and b=1 and c=1 。这个就是 覆盖索引 的概念,意思就是我们的索引正好覆盖了要查询的字段,同时它也是面试官经常会问的为什么不要使用 * 来查询的原因之一。而回表指的就是要到聚集索引中再查找一次,假设普通索引高度为3,聚集索引高度也为3,在普通索引中进行了3次查找,无法使用覆盖索引的话,就需要再去聚集索引进行3次查找,一共需要6次查找。当然,聚集索引的速度是非常快的。不过如果能做到覆盖,肯定还是尽量减少查找更好咯。
注意,覆盖索引默认就是包含主键的,因此在查询语句中出现主键字段是完全没问题的。
总结
今天的内容非常偏概念,但也非常有用,其实 B+树 的内容远不止我讲的这么简单,在页的基础上还有段的概念,还有页段的内部数据结构问题。这些内容大家有兴趣的可以参考更加详细的资料。
整体来说,其实有上面的内容我们就可以大概了解到数据库中的索引以及B+树是如何实现索引的。总之,索引以及相应的知识是我们学习 MySQL 绕不过去的一个坎,也是我们需要不断深入学习的内容,下一篇我们就来看看如何分析一条语句的索引情况。
参考文档:
《MySQL是怎样运行的》
推荐阅读
-
这篇 MySQL 索引和 B+Tree 文章通俗易懂!-创建索引的几个原则
-
MySQL 和 Hive 存储引擎在表、索引数量上有哪些限制?-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 事务隔离级别
-
[MySQL]MySQL索引和B+树的概念
-
[MySQL]索引--从数据页角度看B+树
-
MySQL 索引:为什么索引使用 B+ 树?
-
如何在面试中介绍 mysql 的 B+ 树
-
Mysql]InnoDB 中的聚类索引、二级索引和联合索引
-
理解MySQL基础:主键、外键、索引与唯一索引的概念详解
-
数据结构与算法之美学习笔记:48 | B+树:MySQL数据库索引是如何实现的?-总结引申