数据库是后端工程师绕不开的核心技术，而索引则是核心中的核心。在日常工作中，我们每天都在和索引打交道，它也是高级工程师面试中高频考察的考点。
很多开发者在谈及索引时，往往只能给出一些零散、机械的记忆性答案，比如'B+ 树查询快'、'索引能提速'。这样的回答容易让面试官觉得候选人学习浅尝辄止。真正体现技术深度的，是对索引背后设计原理的系统性理解，以及在复杂场景下进行选型和优化的能力。
在 MySQL 中，通常所说的索引默认指 B+ 树数据结构。在深入探讨各种树结构之前，先明确几个基本概念：
节点：包含数据元素及指向子树的指针。 根节点：树的起始节点，没有父节点。 叶子节点：位于树的最底层，没有子节点。 内部节点：至少有一个子节点的节点，包括根节点和非叶子节点。 兄弟节点：具有相同父节点的节点。 节点的度：该节点拥有的子节点个数。例如二叉树中节点的度最大为 2。 树的度：整棵树中所有节点的最大度数。 高度：当前节点到最远叶子节点的最长路径上的节点数。 平衡因子：每个节点的左右子树的高度之差。 数据页：树上每个节点在计算机中称为数据页，是 InnoDB 存储引擎与磁盘交互的最小单位，默认大小为 16KB。 阶数：一个节点最多可以有多少个子节点，一般用小写字母 m 表示。
在数据库中，我们将 B+ 树作为索引结构以加快查询速度，此时树中的 key 一般是表的主键。MySQL InnoDB 的记录按照主键由小到大排序后，存在 B+ 树的叶子节点里。树中每个节点存储了关键字（key）、关键字对应的数据（data）以及指向孩子节点的指针。我们将一个 key 及其对应的 data 称为一条记录。
不同的树结构适用于不同的应用场景。为了引出为什么 MySQL InnoDB 选择使用 B+ 树，我们需要从基础的树结构开始梳理。
二叉查找树
二叉查找树（Binary Search Tree, BST）也称为有序二叉树，是一棵满足以下性质的二叉树：
- 有序性：任意非空左子树所有节点的值均小于该节点的值；非空右子树所有节点的值均大于该节点的值。
- 递归性：任意节点的子树都是二叉查找树。
- 唯一性：每个节点存储一条记录，且没有键值相等的节点。
这种递归定义简洁地描述了 BST 的结构特点。作为基础的树形结构，每个节点最多有两个子节点，其递归性和有序性为我们理解更复杂的树结构奠定了基础。
如果我们需要查找 id=31 的记录，利用创建的 BST，基于二分查找算法实现的查找流程如下：
- 将根节点作为当前节点，把 31 与当前节点的键值 33 比较，31 小于 33，接下来我们把当前节点的左子节点作为当前节点。
- 继续把 31 和当前节点的键值 28 比较，发现 31 大于 28，把当前节点的右子节点作为当前节点。
- 把 31 和当前节点的键值 31 对比，发现二者相等，满足条件，遍历结束。
所以，利用 BST 只需要 3 次即可找到目标数据。二叉树的查找、插入和删除操作的时间复杂度在平均情况下为 O(logn)，但在最坏情况下，当二叉树退化为链表时，时间复杂度会变为 O(n)。这是因为在最坏情况下，所有节点都在一条链上，查找、插入和删除都需要遍历整个链表。
