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

B-Tree

  • 正整数 d 定义为 B-Tree 的度 Degree
  • 也有一个定义 B-Tree 的属性称为阶 Order，其值为 2d
  • 每个非叶子节点有 n-1 个 key 与 n 个指针，key 与指针相互间隔，key 的两端是指针，d≤n≤2d
  • 每个叶子节点至少包含一个 key 和两个指针，最多包含 2d-1 个 key 与 2d 个指针，叶子节点的指针均为 null
  • 每个节点中 key 从左至右非递减排序
  • 所有叶子节点的深度相同，等于树高 h

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 索引有以下特点

  • 非叶子节点只保存 key 而不保存 data
  • 叶子节点只保存 data
  • B+Tree 的非叶子节点只进行索引不会保存实际记录的指针，所有数据必须要访问到叶子节点才能得到
  • B+Tree 的根节点的 Key 数与子节点数相等
  • 一般会将 B+Tree 进行优化：在叶子节点新增了一个顺序访问的指针，方便对所有的叶子节点进行遍历，提高区间访问的性能

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 列的值

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

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

  • 全值匹配
  • 匹配最左前缀
  • 匹配列前缀
  • 匹配范围值
  • 精确匹配某一列并范围匹配另一列
  • 只访问索引的查询

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

  • 如果不是按照索引的最左列开始查找则无法使用索引，例如上面例子中无法查找名为 Bill 的人，也无法查找特定生日的人
  • 不能跳过索引中的列，上例中索引无法用于查找某确定姓氏，同时又是某日生日的人，因为其跳过了中间一列
  • 如果查询中有某个列的范围查询，则其右边的列都无法使用索引优化查找