文章目录索引简介索引的数据结构选择hash——不支持范围查找二叉搜索树——树高问题导致多次磁盘IOB树B树MySQL中的页为什么要使用页页文件头和页文件尾页主体页目录数据页头B树在MySQL索引中的应用B树的检索过程示例页结果形式MySQL B树可存储记录数的计算示例索引分类主键索引普通索引唯一索引聚集簇索引非聚集簇索引索引覆盖全文索引了解索引简介MySQL的索引是一种数据结构它可以帮助数据库高效地查询、更新数据表中的数据。索引通过一定的规则排列数据表中的记录使得对表的查询可以通过对索引的搜索来加快速度。MySQL索引类似于书籍的目录通过指向数据行的位置可以快速定位和访问表中的数据。比如汉语字典的目录页索引就相当于这个目录页记录关键词在哪一页。不用逐页翻书查询 where 语句时直接跳到目标磁盘区域跳过大量无关数据。为什么要使用索引MySQL所追寻的的两个关键目标安全、效率所以显而易见使用索引的目的只有一个在保证数据安全的基础上最大可能地提升数据检索的效率应用程序的运行过程中查询操作的频率是远远高于增删改的频率的索引的数据结构选择hash——不支持范围查找哈希表查询的时间复杂度O(1)它是最重要的数据结构没有之一但是hash不支持范围查找它的原理的通过hash函数计算出数据的存储位置所以查询速度会很快但是也因此无法进行范围查询如果要查询between .. and..hash就只能一个数据一个数据地查虽然速度很快但是这样查询次数就增加了效率依旧低二叉搜索树——树高问题导致多次磁盘IO二叉搜索树是一种特殊的数据结构左子树根节点右子树它的中序遍历的结果就可以得到一个有序的结果集这样要查询between 20 and 70时就可以先查到20之后直接遍历得到后面数据就可以了但是二叉搜索树遇到特殊的数据时会退化为一个单边树这时时间复杂度就从O(logN)退化为O(N)了而且就算是通过AVL树或者红黑树进行了优化处理了这种特殊情况且处理单叉树本来就是耗时的当节点数目过多时依然会造成树的高度过高而树的高度如果无法控制查询时每当往下一层就要访问一个新的子节点这个操作就是把磁盘的数据加载到内存中进行比对而这样就会增加大量的磁盘IO操作。我们都知道磁盘的数据访问速度是远低于内存的所以磁盘IO是制约所有数据库效率的主要因素所以二叉搜索树无法保证数据库的效率B树B树B-Tree 是一种自平衡的多路查找树专门为处理大规模数据和频繁读写外部存储设备如磁盘、固态硬盘而设计。它的主要目的是减少在查找数据时的磁盘 I/O 读写次数。B树就是一种特殊的N叉树它有以下特点高度平衡所有叶子节点都在同一层保证查找效率稳定。​多分支与多键一个节点可包含多个关键字值和多个子节点指针。​严格有序节点内的关键字升序排列指针所指子树的值落于对应区间内。​节点容量受限每个节点中关键字的数量有明确的上下限B树的阶数满则分裂不足则合并。关键字简单来说它就像是数据的“身份证号”或“检索标签”通常只是一个很小的数据如学号 1001、用户ID 8888B树的时间复杂度时间复杂度O(logN)在数据量相同的情况下B树可以有效的控制树高也就是说可以使用更少的IO次数找到目标节点从而提高数据库的效率但MySQL仍没有使用B树来构建索引MySQL对B树进一步做了优化使用了B树作为实现索引的数据结构B树B树是一种经常用于数据库和文件系统等场合的平衡查找树也是MySQL索引采用的数据结构以4阶B树为例B树与B树的对比数据存储位置​B树所有节点包括根节点、内部节点和叶子节点都存储关键字和对应的数据/数据地址​B 树仅叶子节点存储完整数据非叶子节点仅存储关键字索引​叶子节点连接​B树叶子节点之间独立相互没有指针连接B 树所有叶子节点构成一个单向或双向链表MySQL使用双向链表极其适合范围查询和全表扫描查询效率与稳定性​B树最好情况下在根节点就能找到数据查找时间不固定最快 O(1)最慢 O(log N)​B 树任何关键字的查找都必须走到叶子节点只有叶子节点储存了真实值查找路径长度一致查询效率更稳定均为 O(log N)​单节点容量与树高度​B树非叶子节点存了数据单个节点能容纳的关键字数量较少​B 树非叶子节点只存索引单个节点可容纳更多关键字树的高度更低进一步减少了磁盘 I/O 读写次数接下来我们探讨一下MySQL内部具体是怎么存储数据的MySQL中的页为什么要使用页每创建一个数据库都会在MySQL的数据文件目录下新建一个数据库文件夹如java113在java113数据库中创建表时就会在java113文件夹中新建一个后缀为.ibd的表文件InnoDB存储引擎为每张表生成独立的表空间文件后缀为 .ibd 存储表的数据与索引。在.ibd文件中最重要的结构体就是Page页页是内存与磁盘交互的最小单元默认大小为16KB每次内存从磁盘中读取数据时都至少读取一页所以在磁盘中每个页内部的地址都是连续的之所以这样做是因为在使用数据的过程中利用局部性原理访问一条数据它附近的数据很大概率很快也会被访问所以一次性加载整页预读后续访问同页内的数据直接在内存读取不再访问硬盘大幅减少磁盘IO其实每个表文件就对应着一个B树树中的每个节点就是一个页结构每一个页中即使没有数据也会使用16KB的存储空间查看页大小showvariableslikeinnodb_page_size;扩展Linux操作系统中管理文件的最小单位实际是4KB而MySQL作为一个数据库程序以4KB大小管理数据显然太少了所以定义了16KB一页的默认页大小那么当从内存中往磁盘里写数据页的时候写到一半操作系统挂了这时MySQL应该如何保证数据安全其实在落盘之前会记录各种日志保证重启之后可以找到没有落盘的数据内容先简要了解.ibd文件的具体结构页文件头和页文件尾页头和页尾包含的信息就是一些当前页文件的主要信息这里我们主要关注上一页页号和下一页页号通过这两个属性可以把页与页之间链接起来形成一个双向链表对应B树叶子节点所形成的双向循环链表页主体页主体部分是保存真实数据的主要区域每当创建一个新页都会自动分配两个行一个是页内最小行Infimun另一个是页内最大行Supremun这两个行并不存储任何真实信息而是做为数据行链表的头和尾第一个数据行有一个记录下一行的地址偏移量的区域next_record这样将页内所有数据行组成了一个单向链表此时新页的结构如下所示当向一个新页插入数据时Infimun指向第一个数据行Supremun指向最后一个真实数据行这样数据行就构建成了一个单向链表更多的行数据插入后会按照主键从小到大的顺序进行链接如下图所示页目录在页内查询时发现是一个单向链表时间复杂度为O(N)所以对页内查询仍然有优化MySQL将页内的数据行进行分组最小行单独一组普通分组范围4~8行一组超过8行数据就会分裂为两组那么最大行就永远分到最后一组每创建一个分组就会在页目录中创建一个槽槽的数量与分组的数量是一致的槽会指向其对应分组的最后一条数据存着最后一条记录在页里的偏移地址同时保存这条记录的主键值类比一本书每5~8行文字贴一个小标签槽标签写着这一组末尾行的页码。查找流程在页目录的所有槽上做二分查找对主键值进行二分查找快速判断目标记录在哪一个分组​找到对应的槽之后进入这个分组顺序遍历最多8条记录找到目标行数据页头数据页的头部分为 File Header文件头所有页通用 和 Page Header数据页头File Header管页与页之间的关系存储页编号、上一页与下一页指针、LSN、等等。作用B树链表串联页面、崩溃恢复、校验页是否损坏。​Page Header管页内部的东西存储页内记录数、槽数量、空闲空间、B树层级、等等作用管理页内记录、维护页目录槽、插入/删除数据、判断页分裂。B树在MySQL索引中的应用B树的检索过程示例页结果形式非叶子节点保存索引数据叶子节点保存真实数据如下图所示以查找id为5的记录为例完整的检索过程如下首先判断B树的根节点中的索引记录此时57应访问左孩子节点找到索引页2在索引页2中查找目标是 5按区间匹配规则​小于 3 的在左分支指向数据页1 ​大于等于 3 且小于 5 的在中分支指向数据页2 ​大于等于 5 的在右分支指向数据页3。 ​因为 5 5所以确定目标在右侧分支顺着右侧指针跳转到数据页3找到与5相等的记录以上的IO过程加载索引页1—加载索引页2—加载数据页3共3次IOMySQL B树可存储记录数的计算示例计算三层树高的B树可以存放多少条记录理论上的一个数据页默认16KB我们假设一条数据占1KB那么一页中至多可以存16条数据而索引页中存的是主键值和子节点的引用也就是下一节点的偏移地址主键为 bigint 占 8Byte下一页地址占6Byte也就是说一条索引记录占8614Byte计算像上面的检索过程示例那样根节点为索引页一个索引页可以存 (16*1024)/141170条索引记录这1170条索引记录每个都可以对应第二层的一个索引页而同理第二层的每个索引页都可以指向1170个下一层的页结构也就是叶子节点的数据页共有1170*1170个数据页所以理论上一个三层树高的B树可以存(1170 * 1170) * 1621,902,400条记录在当前的场景下表中的21,902,400条记录通过三次IO就可以完成数据的查询效率非常高索引分类主键索引当在一个表中定义一个主键PRIMARY KEY时InnoDB会自动为该字段创建索引索引就存着主键值普通索引普通索引也叫非唯一索引没有唯一性的限制所以可以有很多行的索引字段一模一样为普通字段创建索引仅仅是为了加速查询允许索引列里面存在重复的值也可以存 null创建索引之后都会生成一棵索引树创建多少索引生成多少棵索引树B树普通索引的B树的叶子节点存的是索引列的值 主键可以看完聚簇索引的概念后再来理解工作中通常为查询频繁的列创建索引且要求列的值重复度不高重复度太高的列建索引收益很差一般不会建。假设一张千万用户表手机号 几乎没有重复重复度很低适合建索引​性别 只有男、女大量重复就算查询 where gender‘男’ 一般不会单独给性别建索引这种情况如果走索引就会查到大量主键大量回表创建索引后生成的索引树也是会占用磁盘空间的写入数据还要维护索引增加开销索引树越多对增、删改的效率影响越大所以创建索引时要慎重考虑一下需不需要复合索引还可以用多个列创建组合索引称为复合索引联合索引多个字段合在一起构建成一棵二级索引树类似于复合主键只不过复合索引是二级索引唯一索引当在一个表上定义一个唯一键UNQUE时自动创建唯一索引。与普通索引类似但区别在于唯一索引的列不允许有重复值跟之前讲的一样唯一索引可以插入 null 可以多个 nullnull 不算重复唯一索引也是属于二级索引除非你把它选做聚簇索引查找如果需要完整字段整行数据同样会回表看完后面的聚簇索引再回来理解主键索引其实本质就是特殊的唯一索引主键不允许重复并且主键不允许为 null。聚集簇索引聚簇索引索引的叶子节点直接存放完整的行数据索引和数据是“簇”在一起的。这时聚簇索引的叶子节点就是数据页保存全部行记录联想之前的B树的图非叶子节点存索引字段的值以便于往下层查找叶子节点存完整的真实数据。一张 InnoDB 表最多只有一个聚簇索引表中存在主键索引InnoDB 就会直接把这个主键索引作为聚簇索引。如果表中没有定义PRIMARY KEY,InnoDB会使用表中第一个UNIQUE且NOT NULL的列作为聚集索引。如果表中没有PRIMARY KEY也找不到非空且唯一的字段InnoDB会为新插入的行生成一个隐藏的行号字段6字节的row_id字段row_id单调递增并使用row_id做为聚簇索引row_id是数据行的隐藏列之一只要是隐藏列我们自己是用不了的无法用 select 去查到这个列也无法用这个列做一些其他的条件查询之类的操作完全是存储引擎内部自己用的非聚集簇索引聚簇索引以外的索引称为非聚簇索引或二级索引回表查询二级索引叶子节点存放的是该索引列的索引值和它的主键和聚簇索引不一样二级索引的叶子节点不会存储完整的真实数据在二级索引的B树找到主键之后再拿着主键走聚簇索引去查找完整行完整数据这个过程就叫回表查询。聚簇索引和二级索引的存储结构总结非叶子节点叶子节点聚簇索引主键 子页地址主键 完整行记录真实数据二级索引索引字段 子页地址索引字段 主键索引覆盖二级索引不一定都会发生回表如果你 select 要查询的全部字段刚好这个二级索引里面都有不需要访问聚簇索引也就是覆盖索引不用回表直接从二级索引就能拿到结果比如假设一张学生表student(idprimarykey,-- 主键聚簇索引name,age,class_id)我们给 name 建立二级索引然后查询selectid,namefromstudentwherename张三;我们想要查询的只有 id 和 name 二级索引叶子节点本身就已经存好了 name 主键 id直接在二级索引拿到全部需要的数据不需要再访问聚簇索引不会回表这种现象就叫做索引覆盖全文索引了解全文索引 fulltext 专门针对长篇文本 varchar / text 做关键词检索代替低效的 like ‘%关键词%’ 。列如一个文章表article (id, title, content)当你想查找正文中包含 “数据库” 关键词的文章时where content like ‘%数据库%’ 全表扫描很慢普通索引失效​给 content 建立 fulltext 全文索引使用 match() against() 检索可以快速找到包含该关键词的记录还会计算相关度这些了解一下就行注意fulltext 只能建立在 char 、 varchar 、 text 这类文本字段上InnoDB、MyISAM 都支持全文索引​中文分词能力弱实际开发很少用 MySQL 自带的全文索引