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。
操作（6个IO）。
（2）右边的一个二叉树索引是Searchcol2=89，也就是2次查找，2次返表操作（2次IO），性能大大提升。
(1)二叉树的特点：左子代码值<节点值；当森林面积很大时，要搜索的数据非常遥远并且没有索引；那么二叉树结构查询的优势就非常明显了。
(2)当搜索一个数字时，当二叉树单向生长时，二叉树就变成了“链式”。
(1)红黑树的特点：每片叶子的节点都是红色或黑色；任何节点的每个叶子都有相同的黑色节点。
（2）现有问题：与二叉树相比，红黑树缓解了过长的问题，但仍然存在存储高度问题。
现在假设数据量为100万条。
红黑树的高度为100,0000=2^n，其中n约为20。
然后，需要至少20个磁盘IO；因此，性能受到很大影响。
磁盘大小越大，IO数量越多，性能损失就越大。
所以红黑树仍然不是最好的解决方案。
上面的红黑树一般每个节点存储一个（索引+磁盘地址），一个节点存储很多（索引+磁盘地址），这样就降低了红黑树的高度。
事实上，我们设想的结构是B-Tree。
（1）哈希索引原理：将经过哈希算法后得到的哈希值（即磁盘文件指针）预先存储在哈希表中。
当他询问时，然后将该索引通过哈希算法以获得哈希值，该哈希值与哈希表中的哈希值进行比较。
通过磁盘文件指针；可以通过单个磁盘IO找到所需的值。
例如，求col=6的值。
hash(6)获取该值并将其与哈希表进行比较，得到89。
非常高的性能。
(2)现有问题：hash表索引有问题。
如果要查询有范围的条件，则无法高效地查询哈希索引。
(1).B-Tree索引特点：B-Tree是一种平衡路由(也叫排序)主要存在于文件系统和数据库系统中，用B表示。
平衡。
描述B树；数据记录是一个元组[key,data]首先设置为key是记录的键值键；由于数据记录不同，key也不同，数据就是一条数据记录。
按关键数据分区（这里称为聚集索引）。
那么B-Tree就是满足以下条件的数据结构：d是大于1的正整数；h称为BTree的度，是一个正整数，称为BTree的高度。
,标记位于节点两端，叶节点深度相同；叶子节点的指针为空，节点中的数据指针从左到右按降序排列。
（2）B+Tree索引特点：B+Tree是在B-Tree的基础上进行的优化，使其更适合实现外部存储索引结构。
在B+树，只有与键值顺序存储在同一层叶子节点上的键值信息才能存储在非叶子位置。
节点降低B+Tree的高度。
(1)聚集索引也称为主键索引。
(2)非聚集索引也称为辅助索引。
处理非聚集索引的过程可以分为两种情况：如果非聚集索引覆盖了索引；我们只需要遍历非聚集索引的B+Tree，如果索引无法被覆盖。
需要对非聚集索引的B+Tree进行两次IO才能进行搜索。
数据行值对应的主键；然后利用主键在聚集索引的B+Tree中查找对应的其他数据。
（1）为什么InnoDB表必须有主键；您会推荐使用整数自动递增主键吗？①次主键索引总是比前一个主键索引大，在进行范围查询时很方便找到需要的数据。
②在安装过程中，因为它是自我增长的；每一个都是稍后插入，UUID大小不确定，但分裂树的机会很小；分裂概率很大，需要树结构。
重新平衡并导致巨大的性能损失。
（2）为什么非主键索引结构的叶子节点存储的是主键值而不是全部数据？①节省空间：指向主键的节点不需要存储相同的数据。
一致性：如果对索引15信息进行更正，只需要更新主键数据，非主键数据也保留一份。
这包括事务一致性问题。
既费时又低效。
(3)为什么要使用封面索引？非捆绑指数是否有指数覆盖范围；我们只需要遍历非聚集索引的B+树就可以从key中获取索引值。
如果索引覆盖不可能。
需要先遍历非聚集索引，获取数据中存储的主键值，然后与IO次数进行比较，来搜索聚集索引中的数据。
多了而且性能比较低。
MyISAM和InnoDB的索引结构对比：MyISAM下的索引结构文件是独立的，InnoDB存储引擎的表数据文件是B+Tree组织的索引文件。
frm文件存储数据表的定义，ibd文件存储索引和实际数据。
InnoDB在搜索数据方面比MyISAM具有更高的性能。

什么是聚集索引、非聚集索引、覆盖索引?

本文旨在解释数据库中覆盖索引的概念，并通过实例进行分析。
在讨论覆盖索引之前，有必要回顾一下索引的基础知识。
索引是数据库管理系统中的排序数据结构，用于加速查询和更新数据库表中的数据。
类似于图书目录，它使数据检索变得高效。
索引可以分为聚集索引和非聚集索引。
聚集索引中键值的逻辑顺序决定了表中对应行的物理顺序。
它通常用于频繁搜索具有特定值的列，例如使用电话簿中的姓名排序来快速查找电话号码。
非聚集索引与磁盘上的物理存储顺序不同，其叶子节点指向对应的数据块地址。
以汉语词典为例，词典正文是聚集索引，按照拼音对汉字进行排序，以便快速查找。
非聚集索引通过部首目录和查词表实现查词，但过程分为两步。
这种结构称为非聚集索引。
索引类型有多种，包括主键索引、普通索引、唯一索引和组合索引等。
其中，主键索引使用主键列作为索引，是最常用的索引类型。
在执行查询时，有时需要从非主键索引树中查找数据，然后返回主键索引树。
这称为“表背”。
回复表会增加性能损失。
为了解决这个问题，引入了覆盖索引。
覆盖索引可以直接从非主键索引中获取所需的数据，避免了回表操作，显着提高了查询性能。
通过建立联合索引，例如（姓名，年龄），可以优化姓名的热门业务，从而提高查询效率。
执行查询时，使用EXPLAIN命令。
如果看到“usingindex”信息，则表示查询使用了覆盖索引。
这说明查询不需要访问主键索引，性能显着提升。