MySQL索引（一）：从数据结构到存储引擎的实现
<blockquote><p>MySQL系列文章</p>
<p>MySQL索引是数据库性能优化的核心知识之一。正确理解索引的原理和使用场景，对于编写高效的SQL语句和设计合理的表结构至关重要。本文将系统介绍MySQL索引的相关知识，包括常见的数据结构、不同存储引擎的索引实现方式，以及聚簇索引和非聚簇索引的区别。</p>
</blockquote>
<h2 id="一索引的常见数据结构及其优缺点">一、索引的常见数据结构及其优缺点</h2>
<p>索引的本质是一种数据结构，用于快速定位数据，就像书的目录一样，可以帮助我们快速找到需要的内容，而不必逐页翻阅。不同的数据结构适用于不同的场景，常见的有以下几种：</p>
<h3 id="1-哈希表">1. 哈希表</h3>
<p>哈希表是一种基于键值对（Key-Value）的数据结构，通过哈希函数将键映射到某个位置，从而快速访问值。</p>
<ul>
<li><strong>优点</strong>：等值查询效率高，时间复杂度为O(1)</li>
<li><strong>缺点</strong>：不支持范围查询，因为哈希表内部数据是无序的；哈希冲突会影响性能</li>
<li><strong>适用场景</strong>：适用于只有等值查询的场景，如Redis等NoSQL数据库</li>
</ul>
<h3 id="2-有序数组">2. 有序数组</h3>
<p>有序数组在等值查询和范围查询场景下都非常高效。</p>
<ul>
<li><strong>优点</strong>：等值查询（二分查找）和范围查询性能都很优秀</li>
<li><strong>缺点</strong>：更新数据时需要移动大量元素，成本高</li>
<li><strong>适用场景</strong>：适用于静态存储引擎，如存储历史数据</li>
</ul>
<h3 id="3-二叉树与平衡二叉树">3. 二叉树与平衡二叉树</h3>
<p>二叉树是经典的数据结构，每个节点的左子节点小于父节点，右子节点大于父节点。</p>
<ul>
<li><strong>优点</strong>：查询和更新时间复杂度均为O(log N)</li>
<li><strong>缺点</strong>：数据量较大时树高较高，查询时需要多次磁盘IO，效率低</li>
</ul>
<h3 id="4-b树与b树">4. B树与B+树</h3>
<p>B树和B+树是为了减少磁盘IO而设计的多路平衡搜索树。</p>
<ul>
<li><strong>B树</strong>：每个节点既存储数据也存储索引，节点大小通常与磁盘块对齐</li>
<li><strong>B+树</strong>：
<ul>
<li>非叶子节点只存储<strong>索引+指针</strong>，叶子节点存储<strong>数据</strong></li>
<li>叶子节点之间通过指针连接，支持范围查询</li>
<li>更适合磁盘读写特性，减少磁盘IO次数</li>
</ul>
</li>
</ul>
<blockquote>
<p>将数据从磁盘读入内存涉及随机IO的访问，是数据库里面成本最高的操作之一。</p>
</blockquote>
<h3 id="innodb主键索引图">innodb主键索引图</h3>
<p><img src="https://img2024.cnblogs.com/blog/3703499/202511/3703499-20251107221305496-2124372209.png"></p>
<blockquote>
<p>主键索引（聚簇索引）：对应B+树结构示意图如上。 B+树是多层的，B+树每一层中的页都会形成一个双向链表。只有<strong>叶子节点存储数据，非叶子节点存储索引值（主键）+指针。</strong></p>
<p>二级索引（非聚簇索引）：结构和主键索引类似，只是<strong>叶子节点存储的不是完整行数据，而是索引键 + 主键ID</strong></p>
</blockquote>
<h4 id="为什么innodb使用b树">为什么InnoDB使用B+树？</h4>
<ul>
<li>磁盘IO次数少：B+树的树高较低，通常只需1-3次磁盘IO即可查询到数据</li>
<li>范围查询高效：叶子节点通过指针连接，便于范围查询</li>
<li>数据有序：B+树叶子节点存储的数据是有序的，适合排序和分组操作</li>
<li>节点利用率高：非叶子节点只存储键值，可以容纳更多索引项</li>
</ul>
<blockquote>
<p>为什么说磁盘IO次数通常在1-3次？</p>
<p>原因：通常来说B+数索引中第一层数据块常驻内存中，第二层其实也极有可能存在内存中，而一个表数10亿数据通常来说也只有4层树高。（下列数据量化）</p>
</blockquote>
<h4 id="b树存储容量量化分析">B+树存储容量量化分析</h4>
<p>假设我们使用bigint作为主键类型（8字节），指针占用6字节，InnoDB页大小为16KB，那么：</p>
<p>每个非叶子节点可存储的键值对数量 = 页大小 / (键大小 + 指针大小) = 16384 / (8 + 6) ≈ 1170</p>
<p>假设每条记录大小约为1KB，那么：</p>
<ul>
<li>每个叶子节点可存储的记录数 = 页大小 / 记录大小 ≈ 16</li>
<li>2层B+树：可存储约1170 × 16 ≈ 18,720条记录</li>
<li>3层B+树：可存储约1170 × 1170 × 16 ≈ 21,902,400条记录（约2200万）</li>
<li>4层B+树：可存储约1170³ × 16 ≈ 25,625,808,000条记录（约256亿）</li>
</ul>
<p>这意味着即使存储数十亿条记录，B+树也只需要3-4次磁盘IO即可找到所需数据，效率极高。</p>
<p>下表总结了常见数据结构的优缺点：</p>
<table>
<thead>
<tr>
<th>数据结构</th>
<th>等值查询</th>
<th>范围查询</th>
<th>插入效率</th>
<th>适用场景</th>
</tr>
</thead>
<tbody>
<tr>
<td>哈希表</td>
<td>○</td>
<td>×</td>
<td>○</td>
<td>等值查询</td>
</tr>
<tr>
<td>有序数组</td>
<td>○</td>
<td>○</td>
<td>×</td>
<td>静态数据</td>
</tr>
<tr>
<td>二叉树</td>
<td>○</td>
<td>○</td>
<td>○</td>
<td>内存数据</td>
</tr>
<tr>
<td>B树</td>
<td>○</td>
<td>○</td>
<td>○</td>
<td>磁盘存储</td>
</tr>
<tr>
<td>B+树</td>
<td>○</td>
<td>○</td>
<td>○</td>
<td>数据库索引</td>
</tr>
</tbody>
</table>
<h2 id="二mysql中常见的索引类型">二、MySQL中常见的索引类型</h2>
<p>MySQL支持多种索引类型，不同存储引擎对索引的支持也有所不同。</p>
<h3 id="1-btree索引">1. BTree索引</h3>
<p>BTree索引是MySQL中最常用的索引类型，基于B+树实现。适用于全值匹配、范围查询和排序操作。</p>
<h3 id="2-哈希索引">2. 哈希索引</h3>
<p>哈希索引基于哈希表实现，适用于等值查询，但不支持范围查询和排序。Memory存储引擎默认支持哈希索引。</p>
<h3 id="3-全文索引">3. 全文索引</h3>
<p>全文索引用于文本内容的模糊搜索和分词查询，适用于CHAR、VARCHAR和TEXT类型的列。InnoDB和MyISAM支持全文索引。</p>
<h3 id="4-空间索引rtree">4. 空间索引（RTree）</h3>
<p>空间索引用于地理数据查询，支持几何数据类型，但使用较少，通常由专用搜索引擎（如ElasticSearch）代替。</p>
<h3 id="不同存储引擎的索引支持">不同存储引擎的索引支持</h3>
<table>
<thead>
<tr>
<th>索引类型</th>
<th>InnoDB</th>
<th>MyISAM</th>
<th>Memory</th>
</tr>
</thead>
<tbody>
<tr>
<td>BTree索引</td>
<td>支持</td>
<td>支持</td>
<td>支持</td>
</tr>
<tr>
<td>哈希索引</td>
<td>不支持</td>
<td>不支持</td>
<td>支持</td>
</tr>
<tr>
<td>全文索引</td>
<td>支持（≥5.6）</td>
<td>支持</td>
<td>不支持</td>
</tr>
<tr>
<td>空间索引</td>
<td>支持</td>
<td>支持</td>
<td>不支持</td>
</tr>
</tbody>
</table>
<h2 id="三聚簇索引与非聚簇索引">三、聚簇索引与非聚簇索引</h2>
<h3 id="1-聚簇索引">1. 聚簇索引</h3>
<p>聚簇索引是一种将数据存储与索引结合的方式，索引的叶子节点直接存储行数据。</p>
<ul>
<li><strong>特点</strong>：
<ul>
<li>一个表只能有一个聚簇索引</li>
<li>数据存储顺序与索引顺序一致</li>
</ul>
</li>
<li><strong>优点</strong>：查询速度快，避免了回表操作</li>
<li><strong>缺点</strong>：插入和更新操作可能引起页分裂，影响性能</li>
</ul>
<p>InnoDB中，主键索引就是聚簇索引。如果没有定义主键，InnoDB会选择一个唯一的非空索引代替，如果没有这样的索引，会隐式定义一个主键作为聚簇索引。</p>
<h3 id="2-非聚簇索引">2. 非聚簇索引</h3>
<p>非聚簇索引的叶子节点存储的是主键值（InnoDB）或数据行指针（MyISAM），而不是行数据本身。查询时需要根据主键值再次查询聚簇索引，这个过程称为<strong>回表</strong>。</p>
<ul>
<li><strong>特点</strong>：
<ul>
<li>一个表可以有多个非聚簇索引</li>
<li>叶子节点不包含行数据，仅存储定位信息</li>
</ul>
</li>
<li><strong>优点</strong>：索引占用空间小，维护成本低</li>
<li><strong>缺点</strong>：查询需要回表，性能略低于聚簇索引</li>
</ul>
<p><strong>重要设计原则</strong>：<strong>主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小</strong>。这就是为什么推荐使用自增整型作为主键，而不是较长的字符串。</p>
<h3 id="3-回表的概念">3. 回表的概念</h3>
<p>回表是指通过非聚簇索引查询时，首先在非聚簇索引树中查找主键值，然后再到聚簇索引树中根据主键值获取行数据的过程。例如：</p>
<pre><code class="language-sql">SELECT * FROM T WHERE k = 5;
</code></pre>
<p>如果k字段上有非聚簇索引，查询过程如下：</p>
<ol>
<li>在k索引树中查找k=5的记录，获取主键值（例如500）</li>
<li>在主键索引树中查找ID=500的记录，获取行数据</li>
</ol>
<h3 id="4-索引维护">4. 索引维护</h3>
<p>索引在提供查询加速的同时，也需要维护成本。当对表中的数据进行增加、删除、修改操作时，数据库需要同步更新相关的索引结构，以保持数据一致性。</p>
<p>B+树为了保持平衡，在数据修改时可能需要分裂或合并节点：</p>
<ul>
<li><strong>插入操作</strong>：可能导致叶子节点分裂，产生额外的磁盘IO</li>
<li><strong>删除操作</strong>：可能导致节点合并，产生空间碎片</li>
<li><strong>更新操作</strong>：相当于先删除后插入，可能同时触发分裂和合并操作</li>
</ul>
<p>因此，索引不是越多越好，需要权衡查询性能和维护成本。对于写多读少的场景，应谨慎添加索引。（通常单表不超过5个为最佳）</p>
<h3 id="5-myisam与innodb的索引实现对比">5. MyISAM与InnoDB的索引实现对比</h3>
<p>尽管MyISAM和InnoDB都使用B+树作为索引结构，但它们的实现方式有本质区别：</p>
<ul>
<li>
<p><strong>MyISAM</strong>：</p>
<ul>
<li>使用非聚簇索引，所有索引都是二级索引</li>
<li>索引叶子节点存储的是数据文件的指针</li>
<li>数据文件和索引文件是分离的（.MYD和.MYI文件）</li>
<li>表数据存储顺序与索引无关</li>
</ul>
</li>
<li>
<p><strong>InnoDB</strong>：</p>
<ul>
<li>主键索引是聚簇索引，叶子节点直接存储行数据</li>
<li>非主键索引是非聚簇索引，叶子节点存储主键值</li>
<li>表数据文件本身就是按主键组织的一个索引结构</li>
<li>支持"索引组织表"特性，数据按主键顺序存储</li>
</ul>
</li>
</ul>
<p><strong>关键区别</strong>：InnoDB是"索引即数据"，主键索引的叶子节点就是数据行；而MyISAM是"索引+数据"，索引和数据分离存储，通过指针关联。</p>
<h2 id="总结">总结</h2>
<p>本文介绍了MySQL索引的常见数据结构、不同类型的索引及其适用场景，以及聚簇索引和非聚簇索引的区别。理解这些基础知识有助于在实际工作中更好地设计表结构和优化查询性能。</p>
<p><strong>索引的出现是为了提高数据查询效率，就像书的目录一样，可以帮助我们快速定位到需要的内容</strong>。InnoDB选择B+树作为索引模型，主要是为了<strong>减少磁盘IO次数，提高查询效率</strong>。通过量化分析可以看出，即使是海量数据，B+树也能在极少的磁盘IO次数内完成查询。</p>
<p>聚簇索引通过将数据存储与索引结合，避免了回表操作，但插入和更新操作可能带来页分裂的问题。非聚簇索引虽然需要回表，但占用空间小，适用于多索引场景。需要注意的是，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小，这也是推荐使用自增整型作为主键的重要原因。</p>
<p>MyISAM和InnoDB虽然都使用B+树结构，但实现方式不同：<strong>InnoDB采用"索引即数据"的聚簇索引设计，而MyISAM使用"索引+数据"的分离式设计</strong>。这一根本区别导致了两者在性能特性上的差异。</p>
<p>在实际应用中，建议根据查询需求和数据特性选择合适的索引类型，并尽量避免回表操作，以提高查询性能。同时需要注意索引维护带来的开销，在读写性能之间找到平衡点。</p>
<blockquote>
<p>文章的最后，想和你多聊两句。</p>
<p>技术之路，常常是热闹与孤独并存。那些深夜的调试、灵光一闪的方案、还有踩坑爬起后的顿悟，如果能有人一起聊聊，该多好。</p>
<p>为此，我建了一个小花园——我的微信公众号「<strong>[努力的小郑]</strong>」。</p>
<p>这里没有高深莫测的理论堆砌，只有我对后端开发、系统设计和工程实践的持续思考与沉淀。它更像我的<strong>数字笔记本</strong>，记录着那些值得被记住的解决方案和思维火花。</p>
<p>如果你觉得今天的文章还有一点启发，或者单纯想找一个同行者偶尔聊聊技术、谈谈思考，那么，欢迎你来坐坐。<br>
<img src="https://img2024.cnblogs.com/blog/3703499/202601/3703499-20260105210259813-964799315.jpg"></p>
<p>愿你前行路上，总有代码可写，有梦可追，也有灯火可亲。</p>
</blockquote><br><br>
来源：https://www.cnblogs.com/xzqcsj/p/19094703
頁:
[1]