在深入探讨MySQL Innodb索引之前，我们先了解几种基本的树形数据结构，包括二叉搜索树、B+树以及B树。 搜索二叉树是一种特殊的二叉树，每个节点至多有两个子节点。左子树上的所有节点值小于其父节点的值，右子树上的所有节点值大于其父节点的值。这种结构有助于快速查找、插入和删除元素，但随着数据量的增长，树的高度会迅速增加，导致查询性能下降，因此不太适合大规模数据存储。 B树是一种自平衡的多路搜索树，适用于文件系统和数据库等大型数据存储场景。B树的特点在于每个节点可以拥有多个子节点，而非仅限于两个。B树的关键性质之一是每个非根节点所含关键字的数量j满足：┌m/2┐ - 1 ≤ j ≤ m - 1，其中m是树的阶数。B树中的每个节点最多有m个子节点。数据不仅存储在叶子节点中，也存储在非叶子节点中。这种结构使得数据能够按照关键字进行有序存储，但由于数据存在于非叶子节点中，顺序遍历较为复杂。 B+树也是一种自平衡的多路搜索树，主要用于数据库系统中，相比于B树，B+树做了如下改进： 非叶子节点不存储数据，只存储指向叶子节点的索引项。所有叶子节点都位于同一层，通过双向链表相连，便于顺序访问。每个节点可以拥有的关键字数量j满足：┌m/2┐ - 1 ≤ j ≤ m。子树的个数最多可以与关键字一样多，非叶节点存储的是子树里最小的关键字。这些特点使得B+树非常适合用于索引构建，特别是在需要频繁顺序访问数据的情况下表现优秀。 B树是一种特殊的B树，具有以下特性： 节点所含关键字的数量j满足：┌m2/3┐ - 1 ≤ j ≤ m。非叶子节点间添加了横向指针，类似于B+树。当一个节点满时，如果它的下一个兄弟节点未满，则将一部分数据移动到兄弟节点中，再在原节点插入关键字，最后修改父节点中兄弟节点的关键字；如果兄弟节点也满了，则在原节点与兄弟节点之间增加新节点，并各复制1/3的数据到新节点，最后在父节点增加新节点的指针。 B*树的设计目标是为了减少分裂次数，提高空间利用率。 索引原理与存储