图解MySQL索引：B-树、B+树

理解MySQL索引的关键在于对B-Tree和B+Tree的深入分析。
这些复杂的数据结构对于提高查询效率至关重要。
本文旨在阐明索引的基本概念和分类，以便在面试时能够准确回答相关问题。
索引是一种数据结构，其主要作用是提高数据查询的效率。
它相当于排序后的快速搜索工具，影响WHERE子句的查询速度和ORDERBY的排序性能。
索引大致分为以下几类：一是按照存储结构，有BTree（B-Tree或B+Tree）、Hash、全文索引和R-Tree；分别是普通索引（单列）、唯一索引（单值，允许空值）和复合索引（又是多列组合，根据数据的物理顺序和逻辑顺序，还有聚集索引（）；InnoDB的B+Tree结构包含数据）和非聚集索引（数据和索引分开存储）。
在底层实现中，哈希索引依赖于哈希表，但只有精确匹配所有列的查询才有效，而B-Tree（MySQL使用B+Tree）通过分布式节点存储提高了Search效率。
InnoDB中的B+Tree索引进一步优化，数据集中在叶子节点，增加顺序访问指针，降低范围查询复杂度。
至于为什么B-Tree不是其他结构，最主要的原因是B-Tree的平衡性和连续性。
哈希索引虽然速度快，但不是顺序的，I/O复杂；二叉树的高度不均匀，红黑树数据量增加，树的高度增加，会影响性能。
自增主键作为索引，由于其连续性，可以有效避免页面分裂和数据移动，提高插入效率。

mysql索引的数据结构，为什么用b+树

B+树是B树的一个小升级。
大多数数据库索引都是基于B+树存储的。
MySQL的MyISAM和InnoDB引擎的索引都是基于B+树存储的。
B+树的最大特点：1.非叶子节点只保留KEY，丢弃DATA2.KEY和DATA一起位于叶子节点，并以链表形式存储（正序、后序或双向）。
3、B+树的搜索与B树不同，当某个节点的KEY与被搜索的KEY相同时。
它跟随KEY左侧的指针。
向下直到关键字到达叶子交集。

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个I/O）才能找到。
（2）右边有一个二叉树索引，用于搜索col2=89，2次搜索就可以找到，也就是2次回表操作（2次I/O操作），性能得到了显着提升。
(1)二叉树性质：左子节点值<节点值；当数据量很大且要查找的数据很远时，与无索引相比，右子节点值>节点值；那么查询二叉树结构的优点就会非常明显了。
（2）当二叉树单向生长时，二叉树就变成了“串”，所以在查找数字时，速度并没有太大的提高。
(1)红黑树的特点：节点为红色或黑色；每个叶子中的节点都是NULL节点；从任何节点到它的每个叶子都包含相同的黑色节点。
（2）存在的问题：虽然红黑树相对于二叉树在一定程度上缓解了单边长度的问题，但仍然受到存储高度问题的困扰。
假设现在数据量为100万条，红黑树的高度约为1000000=2^n，n约为20。
之后，至少需要增加20倍的磁盘I/O操作，所以性能会受到很大影响。
如果数据量越大，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中，所有数据记录节点都按键值顺序存储在同一层的叶子节点上，非叶子节点上只存储键值信息，这样可以大大增加存储的键值数量。
在每个节点中，降低B+Tree的高度。
(1).聚集索引也称为主键索引。
叶子节点中的数据存储了主键对应的整行数据。
(2)非聚集索引也称为辅助索引。
叶子节点中的数据存储的是索引对应的数据行主键的值。
非聚集索引处理过程可以分为两种情况：如果非聚集索引覆盖了索引，则只需要遍历非聚集索引的B+Tree即可，如果索引无法覆盖，则首先需要对B+执行两次I/O操作通过非聚集索引树来查找它。
主键对应数据行的值，然后利用主键在聚集索引的B+Tree上查找其他对应的数据。
（1）InnoDB表为什么要有主键，建议使用自增主键？①后一个主键的索引总是大于前一个主键的索引，在进行范围查询时，很容易找到所需的数据。
②加法过程中，由于是自增，每次加法都是后插的，树分裂的机会小，而UUID的大小不确定，分裂的机会大，树结构必须重新平衡，这会导致显着的性能损失。
（2）为什么非主键索引结构的叶子节点存储的是主键的值而不是全部数据？①节省空间：指向主键的节点不需要存储相同的数据（否则，如果创建多个非主键索引，每个索引上存储的完整数据将占用大量空间）②数据一致性：如果索引15的数据被修改，只需要修改主键数据即可。
如果还存储了一份非主键数据，则必须修改两份。
这就涉及到事务一致性问题，耗时且性能低。
(3).为什么要使用覆盖指数？如果非聚集索引有索引覆盖，我们只需要遍历非聚集索引的B+树就可以从key中获取索引值，并且只需要遍历一棵树。
如果无法进行索引覆盖，则需要先遍历非聚集索引，然后获取数据中存储的主键值，然后遍历查找聚集索引中的数据，对比I/O操作次数比较多，性能比较低。
MyISAM和InnoDB索引结构的比较：MyISAM中的索引结构文件是分开的。
存储驱动器在磁盘上包含三个文件，即电子表格定义文件、索引文件和数据文件。
InnoDB存储引擎本身的表数据文件是按B+Tree组织的索引文件。
frm文件存储电子表格定义，ibd文件存储索引和实际数据。
InnoDB的性能比MyISAM更高搜索数据。