这是一篇发布时间大于两年的文章,当时的一些内容或笔者曾经的思维可能已不再适用于现在,请谨慎判断文章内容的可靠性


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

B-Tree

wzBCGumZ6UxVtr5

  • 正整数 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 进行优化:在叶子节点新增了一个顺序访问的指针,方便对所有的叶子节点进行遍历,提高区间访问的性能

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 索引的一些限制

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