MySQL 中的索引结构

Published: at 09:12 AM

在谈论数据库中的索引时，一般所指的是B-Tree索引

B-Tree

wzBCGumZ6UxVtr5

B-Tree 的检索

查找：首先在根节点二分查找，找到则返回响应节点的数据，未找到则在相应区间指针指向的子节点中递归二分查找，直到查找到指定的 key 表明查找成功，或者到 null 表示查找失败。

插入：我们知道在一个度为 d 的 B-Tree 里，每个节点最多 2d 个子节点，同时除了根节点和叶子节点每个节点至少有 d 个子节点（d≤n≤2d），若根节点不是叶子节点则至少应该有 2 个子节点。要向 B-Tree 中插入一个元素时，首先从根节点查找到这个元素应该位于的位置，若这个节点的子节点数小于最大容量，则可以直接将这个元素插入到应该的位置；若这个节点的子节点数已经到了最大容量，则应当将其插入后从中间一个元素分裂，中间的元素移动到父节点，左边的元素组合作为其左子节点，右边的元素组合作为其右子节点。同样地，若父节点也满，则按照同样的分裂方式继续向上分裂。若到了根节点发现根节点也满了，则将根节点也分裂，中间元素作为顶部一个新的根节点。

删除：在 B-Tree 中删除一个元素时，首先同样地在树中查找到目标元素，然后将其删除，但是由于 B-Tree 的限制：除了根节点与叶子节点每个节点至少有 d 个子节点，根节点至少有 2 个子节点。所以删除后若不满足这个条件即 key 过少，则应首先从子节点取一个元素，若子节点无法取，则向父节点取，然后再将子节点中的中间值替换到原来父节点元素的位置。

B+Tree

与 B-Tree 相比，B+Tree 索引有以下特点

cFLCxa6AV9DI2JP

B-Tree 在 MySQL 的索引中的实现

有这样一个数据表：

CRETE TABLE People(
    last_name varchar(50) not null,
    first_name varchar(50) not null,
    dob date not null,
    gender enum('m','f') not null,
    key(last_name, first_name, dob)
);

对于这个表中的每一行数据，索引中包含了 last_name , first_name , dob 列的值

gJKR7dU3MbvIzx8

如图所示，索引对多个值排序的依据是 create 语句中定义索引时的顺序，如这个表中两个人的姓名均一样，则按照其生日来排序。

可以使用 B-Tree 索引的查询类型

使用 B-Tree 索引的一些限制