一文吃透 MySQL 索引【基础篇】：B + 树入门、简易页存储、索引分类与索引覆盖实战

MySQL索引目录1. 索引简介1.1 索引是什么2. 索引可选数据结构对比2.1 N叉树2.2 B树3. MySQL数据页3.1 为什么要使用页3.2 页基础组成简要说明4. 索引全分类详解4.1 主键索引4.2 普通索引4.3 唯一索引4.4 全文索引4.5 聚簇索引4.6 非聚簇索引4.7 索引覆盖5. 索引实操创建、查看、删除5.1 索引自动创建规则5.2 手动创建单值索引5.3 复合索引创建5.4 删除索引5.5 创建索引避坑要点6. B树在MySQL索引中的应用前言:MySQL 索引是数据库查询优化的核心手段合理使用索引能大幅降低磁盘 IO、成倍提升查询速度是后端开发、面试必掌握的核心知识点。本文为索引基础入门篇重点讲解索引概念、分类与实操InnoDB 页底层完整细节将在以后文章单独深挖。1. 索引简介1.1 索引是什么索引本质是一种用于优化查询效率的数据结构它可以高效协助数据库完成数据表的查找与更新操作通过预设规则有序排列表中记录查询时依托索引检索能够大幅提升查询速度;简单理解没有索引时数据库会逐行遍历整张表建立索引后数据库可通过索引树直接跳转匹配目标数据是解决慢SQL最核心的手段。类比书籍目录通过提前有序存储字段值快速定位磁盘数据避免全表扫描大幅减少IO开销。类比新华字典偏旁目录目录代替逐页翻书索引代替全表扫描快速定位数据大幅减少磁盘IO是优化慢SQL的核心方案。当然新华字典肯定是不止于只有一个目录,拼音,偏旁等等目录来加快我们查找字,这一个个目录也相当于索引,能加快我们查询速度;同理:索引也是一样的; 返回目录2. 索引可选数据结构对比我们之前学习过:顺序表,链表,栈和队列,优先级队列,二叉树,哈希表等等这些数据结构,以及后面会学到的红黑树,AVL树等等,有没有适合作为数据库的索引的呢?我们之前学习的数据结构,都无法适配数据库磁盘读写场景,存在明显的短板,因此MySQL最终选用改良过的B树作为索引的底层结构;简单说明磁盘IO开销远大于内存操作索引结构的核心目标是尽可能降低树的高度、减少磁盘读取次数传统树结构很难满足该需求。在了解B树之前,我们首先先来了解N叉树; 返回目录2.1 N叉树我们常说的B树,就是路平衡N叉树B树,它在二叉树的基础上做了优化,单个节点可以存放多个关键字与节点的分支,能够有效降低树的高度,减少磁盘IO次数;但B树存在明显缺陷根节点、分支节点、叶子节点都会保存完整数据如果执行范围查询需要多次上下跳转多层节点读取磁盘IO开销偏高因此MySQL没有直接选用B树作为索引底层结构。 返回目录2.2 B树B树结构:非叶子索引节点:关键字数量范围(1 ≤ k ≤ m-1)4 阶最多存放 3 个分界 key关键字数量 子指针数量 - 1叶子数据节点:关键字下限[ m/2]-14 阶最少 1 个 key最多 3 个 key节点内关键字升序排列节点间双向指针串联平衡约束:所有叶子节点处于同一层树永远平衡B树特点 :整树天然平衡数据全局有序增删改操作时间复杂度稳定为 (O(log n))非叶子索引节点仅存储分界关键字不存放完整数据记录全部真实业务数据仅保存在叶子节点所有叶子节点通过双向有序链表串联可顺着链表直接遍历全量数据支持连续范围查询索引节点占用空间更小内存可缓存更多路由关键字减少磁盘 IO 次数所有叶子节点高度完全一致查找任意 key 的磁盘访问次数固定性能均衡无波动B树和B树对比:B 树叶子节点有序链表相连区间查询、分页、排序查询效率远高于 B 树B 树区间查询需要多次回溯上层节点B 树非叶子节点的分界关键字全部重复存在于下层叶子节点B 树关键字只出现一次节点自带数据相同阶数、相同数据量下B 树高度更低磁盘 IO 更少B 树节点同时存索引 数据单节点容纳关键字更少B 树无论精确查找还是范围查找都必须走到叶子节点查找耗时稳定B 树可能在中层节点就命中数据查询耗时不固定数据库索引优先选用 B 树文件系统索引多采用 B 树 返回目录3. MySQL数据页在.ibd文件中最重要的结构体就是page(页);页是InnoDB引擎磁盘存储的最小单位默认大小16KB表数据、索引都会存放在数据页内; 返回目录3.1 为什么要使用页依托计算机局部性原理空间局部性说明相邻数据大概率会被访问一次性载入一页数据到缓冲池后续查询同页数据直接读内存大幅减少磁盘I/O。每次内存与磁盘的交互至少读取一页所以在磁盘中每个页内部的地址都是连续的;同时B树索引的每一个节点本质就是数据页可通过系统变量innodb_page_size查看页大小;showvariableslikeinnodb_page_size;换算成字节:16字节局部性原理:时间局部性刚访问过的数据短时间内大概率会再次访问空间局部性 当前访问的数据相邻位置的数据大概率很快会用到。MySQL 数据页就是利用空间局部性一次性加载相邻多条数据到内存减少磁盘 IO。 返回目录3.2 页基础组成简要说明InnoDB 16KB数据页分为7个固定模块各司其职1. 文件头File Header记录页号、前后页关联等全局信息2. 页头Page Header记录本页记录数量、空闲空间等页内状态3. 最小/最大虚拟记录界定页内记录边界方便有序遍历4. 用户记录User Records存放真实表行数据按主键有序排列5. 空闲空间Free Space页内未使用区域用于新增记录6. 页目录Page Directory记录行偏移实现页内快速二分查找7. 文件尾File Trailer校验页完整性防止数据损坏。页的结构我们基础阶段只需要知道页有:页头 数据行 页尾结构就行,后续学习MySQL更深入知识之后,会具体学习页的结构; 返回目录4. 索引全分类详解4.1 主键索引主键索引(primary key) ,inoDB中也叫聚簇索引,数据库中唯一并且非空的核心索引,可以通过primary key约束进行创建;唯一性约束整张表只能存在 1 个主键索引主键字段值绝对不允许重复非空约束主键字段所有行数据不能为 NULL聚簇存储InnoDB主键索引的 B 树叶子节点直接存储完整行数据表数据本身就是主键索引树自动生成建表时指定 primary key 会自动创建主键索引若未指定主键InnoDB 会选唯一非空字段充当聚簇索引无则内置隐藏 6 字节 rowid 作为主键。 返回目录4.2 普通索引最基本的索引类型,没有唯一性约束;一张表可以创建多个普通索引;字段允许存在多条重复数据支持 NULL索引字段可以插入 NULLNULL 值不参与索引排序属于二级索引InnoDB 中普通索引 B 树叶子节点仅存储主键值查询命中索引后需要回表获取完整行数据索引数量没有限制,但普通索引过多 会影响查询速率; 返回目录4.3 唯一索引属于二级索引:当表中定义一个 唯一键unique时自动创建;索引字段的所有值不能重复;可以存在单条null(null不参与与等值对比,多条null会重复判定);InnoDB 底层 B 树叶子节点存储「索引列 主键 ID」查询存在回表逻辑;没有数量限制,单张表能存在多个唯一索引; 返回目录4.4 全文索引仅支持文本类型:char,varchar,text,专门用于关键词全文检索 , 区别于普通 B 树等值 / 前缀匹配索引。InnoDB、MyISAM 两大引擎支持生产环境主流使用 InnoDB作用: 加速文本关键词模糊查询,替代低效的like ,提升海量文本的搜索性能; 返回目录4.5 聚簇索引聚簇索引Clustered Index是 InnoDB 引擎默认主键索引它把整行完整数据和索引存放在同一棵 B 树叶子节点数据行按主键顺序物理排列叶子节点 完整行数据非叶子节点只存主键值 :仅用于索引跳转不存完整数据。优点:1. 查询极快2. 主键查询范围高效3. 数据物理上紧挨在一起,降低IO次数缺点:1. 每一条二级索引都要存储主键,主键越长,二级索引占用磁盘越多,2. 删除大量数据会产生数据页空洞,需要定期整理碎片3. 主键无序的时候会造成页分裂,随机 UUID 作为主键时新数据插入中间频繁拆分数据页写入性能降低 返回目录4.6 非聚簇索引聚簇索引以外的索引;一张表可以有多个非聚簇索引;非叶子节点存储索引字段的值用于快速二分查找叶子节点存储「索引列值 主键 ID」不存完整行数据回表查询:执行普通索引查询时先遍历二级索引 B 树拿到匹配记录的主键再拿着主键去聚簇索引 B 树查找完整行数据两次 B 树 IO 访问这个过程叫回表会增加查询开销 返回目录4.7 索引覆盖当一个select语句使用了普通索引并且查询列表中刚好是创建普通索引时候的部分或者全部列,这时就可以直接返回数据,不需要再一次进行回表查询; 返回目录5. 索引实操创建、查看、删除5.1 索引自动创建规则当我们创建一张表的时候主动加上:主键约束primary key , 外键约束:foreign key , 唯一约束:unique 时,MySQL自动给对应的列创建一个索引;但是如果我们不指定任何约束时,MySQL会默认为每一列生成一个索引并用ROW_ID进行标识;InnoDB 自动生成隐藏ROW_ID6个字节; 返回目录5.2 手动创建单值索引primary key:createtableifnotexiststest(idintprimarykey,namevarchar(20));当然我们也可以通过show keys from 表名或者show index from的方式进行查看主键情况;字段截图值完整含义说明Tabletest索引所属数据表名Non_unique00索引唯一主键/唯一索引1允许重复普通索引Key_namePRIMARY索引名称主键索引固定为 PRIMARY不可自定义Seq_in_index1联合索引内字段顺序单字段索引恒为1Column_nameid创建索引绑定的字段名CollationAA字段升序存储NULL无排序HASH索引Cardinality0索引基数代表字段不重复值预估数量空表默认0影响优化器索引选择Sub_part(Null)前缀索引截取长度NULL代表完整字段索引Packed(Null)字段压缩存储信息NULL表示未压缩Null(Null)字段是否允许NULL主键字段不允许为空故此处无值Index_typeBTREEInnoDB默认B树索引MEMORY引擎支持HASHComment空索引注释建索引时可通过COMMENT指定Index_comment空MySQL8.0新增索引独立注释VisibleYES索引是否对优化器可见INVISIBLE隐藏索引用于灰度测试Expression(Null)函数索引表达式普通列索引为NULL普通索引:方式1:建表时直接定义:createtableifnotexiststest_index(idint,namevarchar(20),ageint,index(age));方式二:已有表追加普通索引createtableifnotexiststest_index(idint,namevarchar(20),ageint);altertabletest_indexaddindexidx_age(age);方式三:create index 单独创建createtableifnotexiststest_index(idint,namevarchar(20),ageint);createindexidx_ageontest_index(age);表结构:唯一索引:unique方式一:建表时直接定义createtableifnotexiststest_index(idintprimarykey,namevarchar(20)unique,ageint);方式二: 已有表追加唯一索引createtableifnotexiststest_index(idintprimarykey,namevarchar(20),ageint);altertabletest_indexadduniqueidx_age(name);方式三:create unique index 单独创建createtableifnotexiststest_index(idintprimarykey,namevarchar(20),ageint);createuniqueindextest_nameontest_index(name);表结构: 返回目录5.3 复合索引创建方式一:创建表时指定;createtableifnotexiststest_index1(idintprimarykey,namevarchar(20),ageint,index(name,age));方式二:修改表中的列createtableifnotexiststest_index1(idintprimarykey,namevarchar(20),ageint);altertabletest_index1addindex(name,age);方式三:单独创建并指定索引名字createtableifnotexiststest_index1(idintprimarykey,namevarchar(20),ageint);createindexindex_1ontest_index1(name,age);查看表索引: 返回目录5.4 删除索引删除主键createtableifnotexiststest_index1(idintprimarykeyauto_increment,namevarchar(20),ageint);showkeysfromtest_index1;我们先创建一个自增主键;语法:altertable表名dropprimarykey;当我们执行的时候:报错了,为什么呢?1075 - 表定义错误只能有一个自动列并且它必须被定义为键意思就是当我们定义主键为自增主键的时候,我们要先删除自增的属性:auto_increment;altertabletest_index1modifyidint;altertabletest_index1dropprimarykey;删除其他索引:语法:dropindex索引名on表名或者altertable表名dropindex索引名;创建一个测试表:createtableifnotexiststest_index1(idintprimarykey,namevarchar(20),ageint,index(name,age));进行删除;dropindexnameontest_index1;-- 或者 : alter table test_index1 drop index name;查看表结构: 返回目录5.5 创建索引避坑要点复合索引等值在前、范围在后遵循最左匹配字段高区分度、少更新字段建索引低基数、频繁修改不建查询禁止索引列运算、隐式转换、前置 % 模糊匹配工程大表低峰建索引小表不建冗余索引多用覆盖索引主键自增数字最优避免超长字符串做主键。 返回目录6. B树在MySQL索引中的应用计算三层B树可以放多少条记录:这里的计算并不需要我们具体的计算出能存放多少条数据,主要考我们的估算能力;索引页一条数据大小:我们知道页默认大小为:16KB 16384 Byte例如: 当主键类型为bigint类型时,主键大小为8Byte,下一页地址为6Byte因此非叶子索引项单条占用空间占用8 6 14 Byte。那么剩余2KB用来干嘛了呢?页基础元数据文件头、页头、校验尾、虚拟记录合计仅 128Byte几乎可忽略页目录 Page Directory存储页内每条记录的偏移地址最多占用约 2KB2048Byte注意这 2KB不是用来存储字段长度字段长度信息分散在每一行记录头部和页目录无关。那么我们有效存储空间:16384 - 2048 ≈ 14336 Byte假设⼀条用户数据大小为1KB在忽略数据⻚中数据页自身属性空间占用的情况下单页存储容量估算非叶子索引页若简化忽略页目录开销16384 / 14 ≈ 1170条索引分叉叶子数据页假设单条完整业务数据1KB一页16KB可存放约16条完整行记录。第 1 层根节点1 个页约 1170个分叉第 2 层中间非叶子层1170个页每个页再分出 1170个分叉第 3 层叶子数据层总数据页数量 1170 * 1170总可存储行数 : 1170 * 1170 * 16 21,902,400条记录约2100W条数据;哪怕单条行数据更大、索引项更少三层 B 树也足以支撑千万级数据表这也是 MySQL 默认只需要 3 层 B 树索引就能覆盖绝大多数业务场景的根本原因。 返回目录