索引（index）是帮助MySQL高效获取数据的数据结构(有序)。在数据之外，数据库系统还维护着满足特定查找算法的数据结构（B+树），这些数据结构以某种方式引用（指向）数据， 这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。
数据结构对比
MySQL默认使用的索引底层数据结构是B+树。再聊B+树之前，我们先聊聊二叉树和B树
二叉搜索树（Binary Search Tree）
二叉搜索树（Binary Search Tree）是一种基于二叉树结构的数据结构，具有以下特点：
每个节点最多有两个子节点：左子节点和右子节点。
对于每个节点，左子节点的值小于该节点的值，右子节点的值大于该节点的值。
通过这种结构，可以实现高效的查找、插入和删除操作，时间复杂度为 O(log n)，其中 n 是树中节点的数量。
最坏二叉树（Worst-case Binary Tree）
最坏情况下，二叉搜索树可能退化成链表结构，导致查找、插入和删除操作的时间复杂度变为 O(n)，这种情况下称为最坏二叉树（Worst-case Binary Tree）。为了解决最坏情况下性能下降的问题，人们提出了各种改进的树结构，其中红黑树就是一种常见的自平衡二叉搜索树。
红黑树（Red-Black Tree）
红黑树（Red-Black Tree）是一种自平衡二叉搜索树，具有以下特点：
每个节点上都带有颜色属性，红色或黑色。
满足以下红黑树性质：
每个节点要么是红色，要么是黑色。
根节点是黑色。
每个叶子节点（NIL 节点）都是黑色。
如果一个节点是红色，则其子节点必须是黑色。
对于任意节点，从该节点到其子孙节点的所有路径上包含相同数目的黑色节点。
通过满足这些性质，红黑树保持了整棵树的平衡，避免了二叉搜索树退化为链表的情况，从而保证了较为稳定的查找、插入和删除操作的时间复杂度为 O(log n)。
总结来说，二叉搜索树是一种基本的数据结构，但在最坏情况下性能可能下降；最坏二叉树表示二叉搜索树在最坏情况下的状态；而红黑树则是一种自平衡的二叉搜索树，通过维护特定的性质来保证树的平衡性。
BTree
BTree，B树是一种多叉路衡查找树，相对于二叉树，B树每个节点可以有多个分支，即多叉。以一颗最大度数（max-degree）为5(5阶)的b-tree为例，那这个B树每个节点最多存储4个key
B树是一种多路平衡查找树，每个节点可以包含多个子节点。
每个节点中既存放数据，也存放索引，数据节点和索引节点的结构相同。
在B树中，每个节点都包含了关键字和对应的子树指针。
B树的特点是所有叶子节点位于同一层，且叶子节点之间通过指针连接，可以支持范围查询。
B+Tree
B+Tree是在BTree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构
B+树也是一种多路平衡查找树，但只有叶子节点存储数据，非叶子节点只存储索引。
叶子节点通过指针连接形成链表，便于范围查询和顺序遍历。
非叶子节点只包含索引信息，不存储数据，可以容纳更多的索引，减少树的高度，提高检索效率。
B+树的特点是所有数据都存储在叶子节点中，非叶子节点仅用作索引，有利于减少磁盘I/O次数。
B树与B+树对比:
①：磁盘读写代价B+树更低；
②：查询效率B+树更加稳定；
③：B+树便于扫库和区间查询