MySQL索引的底层数据结构原理剖析(二叉树、红黑树、Hash、B-Tree、B+Tree)

我们通常所说的：聚集索引（主键索引）、二级索引、覆盖索引、复合索引、前缀索引和唯一索引在MySQL5.7和8.0版本中默认使用B+Tree索引。
此外，还有哈希索引。
至于MySQL5.7之前的版本，这里不再赘述。
查看各种数据结构图解网站：cs.usfca.edu/~galles/visualization/Algorithms.html（推荐）下图中，左边的表没有索引，右边的表是二叉树索引，有col2作为索引列。
下图说明了索引和非索引之间的区别。
解析如下SQL语句：select*fromtwherecol2=89;(1)左边没有索引。
搜索col2=89需要从上到下搜索，或者6个表返回。
操作（6个IO）。
（2）。
右边是二叉树索引。
搜索col2=89，2次查找就可以找到，也就是2次回表操作（2次IO），性能大大提升。
(1)二叉树的特点：左子节点的值<该节点的值；当数据量很大且要查找的数据很远时，与无索引相比，右子节点值>节点值；那么二叉树结构查询的优势就会非常明显。
（2）。
当二叉树单边扩展时，二叉树就变成了“串”，所以在查找数字时，速度并没有得到很大的优化。
(1).红黑树的特点：节点为红色或黑色；根节点为黑色；每个叶子的节点都是黑色空节点（NULL）；从任何节点到它的每个叶子都包含相同的黑色节点。
（2）现有问题：虽然红黑树相比二叉树在一定程度上缓解了一侧过长的问题，但它仍然存在存储高度的问题。
假设现在数据量为100万，红黑树的高度约为10万=2^n，n约为20。
那么至少需要20倍的E/S盘，所以性能会受到很大影响。
如果数据量和I/O数量越大，性能损失就会越大。
所以红黑树仍然不是最好的解决方案。
上面的红黑树默认每个节点存储一个（索引+磁盘地址）。
我们想象一个节点存储几个（索引+磁盘地址），这样红黑树的高度就可以降低。
事实上，我们正在考虑的结构是B-Tree。
（1）哈希索引原理：索引经过哈希算法后得到的哈希值（即磁盘文件指针）预先存储在哈希表中。
查询时，索引经过哈希算法得到哈希值，与哈希表中的哈希值进行比较。
使用磁盘文件指针，可以通过单个磁盘I/O找到所需的值。
例如，要查找值col=6。
hash(6)获取值并与哈希表比较，得到89。
性能非常高。
（2）。
现有问题：哈希表索引存在问题。
如果要查询有范围的条件，哈希索引无法高效查询。
(1).B-Tree索引的特点：B-Tree是一种平衡（也称为排序）多路径搜索树。
它被用在系统中文件和数据库系统。
它主要用作文件的索引。
平衡。
为了描述B-Tree，首先将一条数据记录定义为一个[key,data]元组，key是该记录的键值key，对于不同的数据记录，key彼此不同，data是数据记录；除以关键数据（这是聚集索引）。
那么B-Tree是一种满足以下条件的数据结构：d是大于1的正整数，称为BTree的度；h是一个正整数，称为BTree的高度，指针之间的距离；，并且指针位于节点的两端。
;叶子节点深度相同，叶子节点指针为空，节点中的数据索引从左到右升序排列。
（2）B+Tree索引的特点：B+Tree是在B-Tree的基础上进行的优化，这使得它更适合实现外部存储索引结构。
在B+Tree中，所有的数据记录节点按照key值的顺序存储在同一层的叶子节点上。
非叶子节点上只存储键值信息。
这可以显着增加每个存储的键值的数量。
节点.节点。
，降低B+Tree的高度。
(1).聚集索引也称为主键索引。
叶子节点数据存储了主键对应的整行数据。
（2）。
非聚集索引也称为辅助索引。
叶子节点数据存储索引对应的数据行的主键值。
寻址非聚集索引的过程可以分为两种情况：如果非聚集索引已经被覆盖，则只需要遍历非聚集索引的B+Tree即可。
如果索引无法被覆盖，则必须先在非聚集索引的B+Tree上执行两次IO才能找到它。
找到与数据值行匹配的主键，然后使用该主键在聚集索引的B+Tree上查找其他匹配的数据。
(1).为什么InnoDB表需要主键，建议使用自增整数主键？①下一个主键索引总是大于前一个主键索引。
在范围查询时，可以非常方便地找到所需的数据。
②在append过程中，由于是自增，每次append都是后来插入的，树分裂的风险小；虽然UUID的大小不确定，但分裂的风险很高，必须重新平衡树结构，导致显着的性能损失。
(2).非主键索引结构的叶子节点为什么存储主键值而不是全部数据？①节省空间：指向主键的节点不需要存储相同的数据（否则，如果建立多个非主键索引，每个上存储的完整数据将占用大量空间）②数据一致性：如果修改索引15的数据，只需要修改主键数据即可。
如果还存储了非主键数据的副本，则必须修改两份。
这就涉及到事务一致性问题了，也就是。
耗时且性能低下。
(3).为什么要使用覆盖率指数？如果索引覆盖在非聚集索引中可用，那么只需遍历非聚集索引的B+Tree即可获取该key的索引值。
我们只需要遍历一棵树。
如果无法进行索引覆盖，则必须先浏览非聚集索引，然后获取数据中存储的主键值，然后再浏览聚集索引中查找数据。
与索引覆盖率相比，I/O数量。
比较多，性能比较低。
MyISAM和InnoDB的索引结构比较：MyISAM下的索引结构文件是不同的。
存储引擎在磁盘上有3个文件，分别是数据表定义文件、索引文件和数据文件。
InnoDB存储引擎表数据文件本身就是一个按B+Tree组织的索引文件。
frm文件存储数据表定义，ibd文件存储索引和实际数据。
InnoDB在搜索数据时比MyISAM具有更高的性能。

mysql的索引有哪些

MySQL的主要索引如下：1、B树索引（INDEX或KEY）：最基本的索引，用于快速定位数据。
大多数MySQL存储引擎（例如InnoDB和MyISAM）都使用B树结构进行索引处理。
通过建立有序的数据结构，可以快速确定记录的位置。
查询数据时，通过索引可以快速找到对应的数据块，大大提高查询效率。
2、哈希索引（HASH）：适合等价查询，可以快速定位数据的具体位置。
MySQL中的MEMORY存储引擎支持哈希索引。
哈希索引的特点是通过根据键值计算哈希值来快速查找数据。
它在同值查询上具有较高的性能，但在范围查询上性能较差。
需要注意的是，哈希索引无法避免不同节点之间数据的聚合。
因此，在有大量重复键值的列上设置哈希索引并不是最优的选择。
另外，如果内存中的哈希表占用量较大，也会影响性能和存储空间。
因此，在实际应用中，需要根据具体情况决定是否使用哈希索引。
3.空间索引（R-tree）：主要用于索引点、线、多边形等空间数据类型。
MySQL的MyISAM存储引擎支持空间索引。
空间索引主要应用于空间数据的范围查询、邻近查询等场景。
空间索引可以显着提高空间数据的查询效率。
空间索引适用于地理信息系统等应用场景。
此外，还有一些其他特殊的索引类型，例如全文索引等，这些索引类型可以在某些特定场景下提供高效的查询性能。
4.复合索引：复合索引是由多个列组成的索引。
创建复合索引时，您需要考虑如何对列进行排序和组合，以便在查询时可以充分利用索引。
复合索引适用于需要基于多列进行条件查询的场景，可以提高查询效率，减少数据库的负载。
需要注意的是，复合索引的列顺序和组合需要根据实际情况进行优化，才能充分发挥其性能优势。
简而言之：MySQL提供了多种类型的索引来满足不同应用场景的需求。
在实际应用中，需要根据数据的特点和查询需求选择合适的索引类型，并对其进行优化和调整，以达到最佳性能。

mysql索引一般使用什么数据结构

mysql索引常用的数据结构有：1.普通索引：无一例外的基本索引。
2.唯一索引：与“普通索引”类似，不同的是索引列的值必须是唯一的，但不允许有任何值。
3、主键索引：是一种特殊的唯一索引，不允许有任何值。
4.全文索引：只能用于MyISAM表。
对于较大的数据，生成全文索引非常耗时且需要大量空间。
5、链接索引：为了提高MySQL的效率，可以建立链接索引，遵循“左前缀”的原则。