BTree和B+Tree的比较，你了解了么？-每日运维

我们都知道在 Mysql 中，索引是非常重要的内容，因为他对我们的查询会有非常大的帮助，所以，我们今天就来看看这个 Mysql 的索引。

Mysql 索引

B-Tree索引：

这是MySQL中最常用的索引类型，基于B-Tree（平衡树）数据结构。
InnoDB、MyISAM、Memory存储引擎都使用B-Tree索引。
B-Tree索引能够处理全值匹配和范围查询，并且能够按照索引列的顺序进行排序。

B+Tree是一种自平衡的树结构，它维护了排序数据的索引。与二叉树不同，B+Tree的每个节点可以有多个子节点（这个数量通常称为“阶”或“度”）。树中的每个节点都存储了键和指向子节点的指针。但与B-Tree不同的是，B+Tree的非叶子节点不存储数据，只存储键和指针，而所有的数据都存储在叶子节点中。此外，B+Tree的叶子节点之间通过指针链接，这样可以方便地进行范围查询。

哈希索引

主要用于MEMORY存储引擎。
基于哈希算法，只支持等值查询，不支持范围查询。
查询速度非常快，但不适合有排序需求或范围查询的场景。

空间索引（SPATIAL）

用于处理空间数据，如点、线和多边形等。
基于R-Tree数据结构，用于地理空间数据类型的字段。
主要在MyISAM存储引擎中使用，但从MySQL 5.7开始，InnoDB也开始支持空间索引。

对于空间数据类型（如点、线和多边形），MySQL提供了空间索引来支持高效的空间查询。空间索引基于R-Tree数据结构实现，可以快速地定位到满足查询条件的空间对象。空间索引在GIS（地理信息系统）和LBS（基于位置的服务）等应用中非常有用。然而需要注意的是，空间索引只在MyISAM存储引擎中直接支持；在InnoDB中则需要使用额外的扩展或技巧来实现类似的功能。但从MySQL 8.0开始，InnoDB也开始支持空间索引了。

全文索引（FULLTEXT）

主要用于MyISAM存储引擎（尽管从MySQL 5.6开始InnoDB也支持全文索引）。
用于在文本列上进行全文搜索，支持自然语言查询、布尔查询和查询扩展。
全文索引在创建时会创建一个包含所有单词的索引，查询时能够快速找到包含特定单词的行。

聚簇索引与非聚簇索引

这不是一种单独的索引类型，而是描述索引与数据行之间关系的术语。
在InnoDB中，表总是有一个聚簇索引（通常是主键索引），数据行实际上存储在聚簇索引的叶子节点中。
非聚簇索引（二级索引）的叶子节点存储的是指向数据行的指针或主键值。

复合索引：

由多个列组成的索引。
可以提高多个列上的查询性能，但需要注意索引列的顺序和查询条件的使用方式。
复合索引遵循最左前缀原则，即查询条件需要包含索引的最左边的列才能有效利用索引。

唯一索引：

确保索引列中的所有值都是唯一的。
可以在一个或多个列上创建唯一索引。
主键索引是一种特殊的唯一索引，它不仅要求值是唯一的，还要求每个值都不能为NULL。

我们说完了这个索引的分类之后，我们就来看看经典的 Mysql 默认的 InnoDB 引擎的所使用的 B+Tree索引

B+Tree索引

B+Tree索引是数据库中最常用的索引类型之一，特别是在像MySQL这样的关系型数据库中。B+Tree（B-Plus Tree）是B-Tree的一种变种，它提供了更高的查询性能，特别是在处理大量数据和进行范围查询时。

MySQL数据库索引采用的是B+Tree结构，在B-Tree结构上做了优化改造。B-Tree结构：

索引值和data数据分布在整棵树结构中

每个节点可以存放多个索引值及对应的data数据

树节点中的多个索引值从左到右升序排列

图片

B-Tree（平衡树）的搜索过程

B-Tree（平衡树）的搜索过程是一个相对直观且高效的操作，它利用了树的结构特性来快速定位到需要查找的数据。以下是B-Tree搜索的基本步骤：

1.从根节点开始：搜索操作总是从B-Tree的根节点开始。

2.比较关键字：在当前节点内，从左到右顺序比较关键字。找到第一个大于或等于目标关键字的关键字项，或者找到当前节点中的最大关键字项（如果所有关键字项都小于目标关键字）。

3.决定搜索方向：

如果找到的关键字项等于目标关键字，则搜索成功，返回该关键字项所在的节点和位置。
如果找到的关键字项大于目标关键字，并且当前节点是叶子节点，则搜索失败，目标关键字不存在于树中。
如果找到的关键字项大于目标关键字，但当前节点不是叶子节点，则在当前节点的子节点中继续搜索。选择找到的关键字项左侧的子节点作为下一步搜索的起点（因为B-Tree的性质保证了左侧子树中的所有关键字都小于当前节点的这个关键字项）。
如果所有关键字项都小于目标关键字，并且当前节点不是叶子节点，则在右侧子节点中继续搜索（同理，右侧子树中的所有关键字都大于当前节点的最大关键字项）。

4.递归搜索：重复步骤2和3，直到找到目标关键字或确定关键字不存在于树中。

5.处理叶子节点：当搜索到达叶子节点时，如果叶子节点中包含目标关键字，则返回该节点和关键字的位置；否则，搜索失败。

B+Tree的结构

B+Tree（B-Plus Tree）是一种自平衡的多路搜索树，广泛应用于数据库和文件系统的索引结构。它是B-Tree的一种扩展，具有一些独特的性质和优化，使得它在某些场景下比B-Tree更加高效。

图片

B+Tree的搜索过程与B-Tree类似，但由于B+Tree的数据只存储在叶子节点，并且叶子节点之间通过指针相连，所以搜索过程有一些不同。以下是B+Tree搜索的基本步骤：

1.从根节点开始：搜索总是从B+Tree的根节点开始。

2.在内部节点中搜索：在每个内部节点（非叶子节点）中，从左到右顺序比较关键字。找到第一个大于或等于目标关键字的关键字项，然后转到与之关联的子节点。如果没有找到大于或等于目标关键字的关键字项，则转到当前节点中最大关键字项右侧的子节点（如果存在的话）。

3.递归下降：重复步骤2，直到到达一个叶子节点。

4.在叶子节点中搜索：在叶子节点内顺序搜索目标关键字。如果找到匹配项，则返回该匹配项及其对应的数据记录（或指向数据记录的指针）。如果没有找到匹配项，但叶子节点中存在相邻的节点指针，并且搜索是范围查询的一部分，则可以使用这些指针继续搜索。

5.处理范围查询：如果搜索是范围查询（例如，查找所有大于某个值的数据项），则在找到第一个匹配项后，可以沿着叶子节点间的链表继续搜索，直到找到范围外的第一个数据项为止。

6.结束搜索：如果遍历完所有可能的路径仍然没有找到目标关键字，则搜索失败，表示该关键字不存在于B+Tree中。