了解MySQL索引数据结构足以从现在开始不再可爱

您将尽可能大胆地进行生产！搜索微信公众号（达摩克斯的笔）以获取更多资源，并在文章末尾附上QR码！

Github地址: 不断收集更新的数据

在进行优化时，要添加一个索引. 如果您不使用它，请转到“为解锁系列”索引已为您准备好！如果您像我一样从未理解过索引的基础数据结构，无知的X树上的无知的X水果，以及您和我在无知的X树下的无知，请在下面给我留言，告诉我多个，我感觉好多了，但是现在我有了Wuoo，在阅读了整篇文章之后，我相信您像我一样，扬起雾气对天晓说: 是吗？就是这样，让我们​​直言不讳！

索引主要包括哈希表，二叉树，红色和黑色树，B树和B +树. 我们的MySQL使用B +树！

哈希索引是基于哈希表实现的. 对于数据的每一行，存储引擎都会为所有索引列计算哈希码. 哈希码是一个较小的值. 将所有哈希码存储在索引中，并保存指向哈希表中每个数据行的指针. 如果哈希码相同，则将以链接列表的形式存储，类似于HashMap，哈希索引适合精确查询.

有下表

如果我们在名称列中创建索引，则名称将使用哈希算法来计算名称列中每行数据的哈希值并将其存储. 由于哈希值是随机计算的，因此，如果计算结果如下，则可能会发生冲突

哈希索引数据结构如下

我们有一个SELECT ID，名称，年龄，从t_user那里WHERE name ='Shi Xiaotian';这样的SQL可以根据哈希算法直接为Shi Xiaotian计算Hash值，通过该值找到对应的记录指针，并传递记录. 该指针查找表中数据的哪一行，最后比较名称是否为Shi小天确保要找到该行.

但是如果我们有SELECT id，名称，年龄FROM t_user WHERE名称>'Shi Xiaotian';这样的SQL是无能为力的，因为Hash表支持快速精确的查询，但不支持范围查询.

二叉树是每个节点最多具有两个子树的树结构. 通常，子树称为“左子树”（左子树）和“右子树”（右子树）. 二进制树通常用于实现二进制搜索树和二进制堆.

向id列添加索引会使用二进制树进行存储，如下所示

如果我们的数据是单边增长的，最终的二叉树可能会变成一个链表，我们将查询数据如下所示

如果有一个SQLSELECT ID，名称，年龄FROM tb_user WHERE ID = 7，请在此字段上创建索引，并使用二叉​​树来维护它查找6次，速度与不创建索引相同！

当索引字段连续或在其他情况下时，二叉树索引的性能很低，并且树严重不平衡，因此我们引入了红树和黑树

红黑树（Red Black Tree）是一种二进制搜索树，其中包含红色和黑色节点，并且可以自我平衡. 它是一棵平衡的二叉树. 红黑树的每个节点都有代表该节点的存储颜色，可以是红色或黑色

类似地，添加id列的索引以使用红色和黑色的树进行存储. 如下图所示，我们将进行调整以使树相对平衡. 较小的值位于上级节点的左侧，较大的值位于上级节点. 节点正确

相同的查找相同的4和7两个数据，如下所示

很明显，在使用红黑树之后，与二叉树相比，树更加平衡，搜索数据更快. 为什么MySQL仍不使用此数据结构来维护索引数据？让我们在下面进行分析并完成

通过上面的红色和黑色树，我们可以发现数据越多，高度越高. 树越高，查询数据的次数就越多. 我们可以通过控制树的高度来控制查询的数量. 这是我们的B树即将完成伟大的事业，因此您不妨喝一杯茶，并考虑在红色和黑色树的基础上将树的高度控制为3-5层，并且然后存储数千万的数据. 如果你呢？

二叉树和红黑树都在一个节点上存储一个数据，而B编号基于红黑树在一个节点上存储多个数据. 所谓的B树，B树和B树都说同一件事，全称Balance-tree被翻译为平衡的多向搜索树，并且平衡在左右均匀分布. ·多路径是相对于二叉树的. 二叉树是一种双向搜索树. 搜索时只有两条路，B树有多条路径，即父节点有多个子节点. 看图片聊天

查看存储在B树中的数据. 保存后，总共有四个节点，其中2个存储节点，4个存储节点，1个节点，3个节点，6，7个节点，1小于2，所以1在2的左侧，在侧面， 3大于2且小于4，因此在2的右侧的2的左侧，2和4存储在同一节点上，而6和7大于4，因此它们存储在一个节点上在4的右侧

看着B树来获取数据，我们第一次带4个节点直接找到数据，第二次获取7个，然后两次找到该节点以确定位置

B + Tree是B-Tree的变体，MySQL使用B + Tree作为索引数据结构，如图所示

B +树保存数据

B +树获取数据

数据和节点都需要空间存储. 如果删除数据，则可以存储更多节点. MySQL中使用的B +树的每个节点最多可以存储16KB的数据. 您可以传递SHOW GLOBAL STATUS LIKE'InnoDb_page_size';这个SQL查询. 在16KB的情况下索引 数据结构，MySQL可以使用B + Tree存储更多的索引元素. 如果表id使用bigint作为索引，占用8Byte，并使用6Byte记录该节点的子节点的位置，则索引字段占8 + 6 = 14Byte，16KB / 14Byte = 1170，每个节点可以存储1170个元素

在上面，我们计算出每个节点可以存储1170个元素，并且每个节点都有子节点. 如果树高为3，则每个索引占用1KB. 这个1KB并不小，因此可以存储1170 *1170. * 16 = 2190W的数据，完全可以满足我们数以千万计的数据表的查询

B +树中的非叶节点在叶节点中将是冗余的，并且叶节点通过指针连接. 初始哈希不支持范围查询. 二叉树的高度很高，只有B树和B +具有. 相比之下，B树节点可以存储多个元素，相对于红黑树而言，整体树的高度降低了，磁盘IO效率为改善. B +树是B树的升级版本，仅使非叶节点冗余. 这样做的优点是提高了范围搜索的效率. 改进的原因无非是指向下一个节点的叶子节点的指针

这里我们介绍哈希，二叉树，红黑树，B树，B +树的每种数据结构，并得出结论索引 数据结构，Mysql使用B +树作为维护索引的数据结构，可以改善查询指数. 磁盘IO效率，并且可以提高范围查询的效率，并且B +树中的元素也被排序. 接下来，让我们讨论一下Mysql中两个常见的存储引擎如何使用索引

CREATE TABLE `tb_myisam` (
  `id` int(11) NOT NULL,
  `col1` varchar(255) DEFAULT NULL,
  `col2` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

创建myisam表后，磁盘上将维护三个文件frm，MYD和MYI

frm: 存储表结构

MYD: 存储表数据

MYI: 存储表中的索引

insert into tb_myisam (id,col1,col2) VALUES
(2,"测试数据2","测试数据22"),
(4,"测试数据4","测试数据44"),
(5,"测试数据5","测试数据55"),
(7,"测试数据7","测试数据77"),
(1,"测试数据1","测试数据11"),
(3,"测试数据3","测试数据33"),
(6,"测试数据6","测试数据66");

SELECT id,col1,col2 FROM tb_myisam

您可以看到数据排序方法是根据插入顺序排序的

在id列中创建索引，左上角是B + Tree中的数据维护结构，右下角是数据表数据，B + Tree叶节点下面的数据存储对应的磁盘地址到数据行. 来自tb_myisam WHERE id = 3的SELECT id将首先在索引文件中找到3节点，然后取出相应的磁盘地址，并在MYD文件中找到此数据行以实现查询.

CREATE TABLE `tb_innodb` (
  `id` int(11) NOT NULL,
  `col1` varchar(255) DEFAULT NULL,
  `col2` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

创建InnoDB表后，磁盘上将存在两个文件frm，即ibd维护

frm: 存储表结构

ibd: 存储表索引和数据

insert into tb_innodb (id,col1,col2) VALUES
(2,"测试数据2","测试数据22"),
(4,"测试数据4","测试数据44"),
(5,"测试数据5","测试数据55"),
(7,"测试数据7","测试数据77"),
(1,"测试数据1","测试数据11"),
(3,"测试数据3","测试数据33"),
(6,"测试数据6","测试数据66");

mysql主键自动创建一个索引，innodb搜索引擎按主键排序

InnoDB存储引擎，表数据文件（即ibd文件本身）是根据B + Tree进行组织的索引结构文件，并且叶节点包含完整的数据记录

您应该说InnoDB表必须有一个主键，建议将此主键使用整数自动增量. 如果表中有主键，则将在主键上添加索引以对其进行维护. 如果在创建表时未指定主键，则将在表中找到要维护的唯一数据列. 如果找不到此类列，则将默认添加一列以进行维护.

建议使用整数类型. 首先，整数存储占用较少的空间，排序时速度更快. 一些公司可能使用UUID作为主键. UUID是随机字符串，需要在比较之前进行转换. 比较并占用大量空间，因此不建议使用

建议使用自动增量，因为我们的叶节点数据是从左到右顺序排序的，这在进行范围查询时更加方便. 如果您的值是随机的，则可能会修改树的原始结构，从而导致分裂和分裂. 开放会影响性能，您可以看到下面的示例，我们最后添加8以查看更改

在开发项目时，通常不创建单列索引，而是创建联合索引的多个键. 现在，只要您了解了联合索引的基本原理，就可以了解Internet上MySQL索引优化的基本原理. ，不必回到我身边，我讨厌记住事情，记住后立即忘记，下面的图片是联合索引的外观

假设我们的联合索引为（col1，col2，col3），即上方绿色正方形中的三行数据，并根据其他三列未索引字段按col1，col2，col3，purple排序，在这里了解联合索引的顺序是什么，最左边的前缀规则是什么，索引为什么会失败，以及索引优化文章为什么要求您编写此索引，我认为您应该在思考后理解它！必须勤于思考！

“高性能MySQL”

“ MySQL技术内幕: InnoDB存储引擎”

首先，我非常感谢读者关心该工具的内在想法. 谢谢你照顾我的眼泪. 把它拉下来很好奇. 感谢您的关注和称赞. 第二个是一些想法. 这篇文章确实花费了很多时间和精力. 对基本原理的研究越多，我发现我所知甚少. 为了写这篇文章供大家理解，这也是加入的第一篇文章. ，创建软件需要花费一些精力. 我什至没有谈论学习和阅读的时间. 我也学到了自己. 哈哈，我之前写的博客都是关于技术的使用的，因为我认为每个人都是我的博客之一. 技术可以从小白到精通，再到先进，但发现确实存在着有限的能量，互联网上到处都有技术进入，每个人都应该看到一些原理性的水平，思想水平的文章，以提高自己的水平. 大植物收割提供的不仅是停留在初级阶段，我们还需要快速增长，因此以下文章重点介绍原理层，思维层，产品，学习路线等文章. 对于入门白，您可以看到文章的学习路线系列，工作1-三年来，朋友可以阅读有关原理层，构想和体系结构的文章. 大约5年的时间，朋友可以看看产品. 从宏观的角度来看，如何识别一个好的产品设计是好的，一个资深的人，我也讨厌被限制的能力没有出来，以为耻.

创建起来并不容易，代码很难，有时我会头晕目眩，没有主意，但是我一直坚持，我希望喜欢有帮助的朋友** [不要拜拜] **，记住喜欢它，在问题下留言，或者按照公共帐户添加微信朋友，QQ朋友等互相讨论，共同成长，不再在同一个地方迷路，不再被同事压倒，不再欣赏别人，而成为别人关注的焦点

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-170790-1.html