为什么说"B+树索引适用于全键值,键值范围或者最左键前缀查找"? 看高性能 Mysql 的困惑

周梦康
  • 8.9k

还以书上例子来说

sqlcreate table people(
    last_name varchar(50) not null,
    first_name varchar(50) not null,
    dob date not null,
    gender enum('m','f') no null,
    key(last_name,first_name,dob)
);

图片描述
这个 B+tree 的索引示意图能明白,但是为什么马上在下文就说"B+树索引适用于全键值,键值范围或者最左键前缀查找"
我应该如何去理解,是否和 B+tree 有着不可分割的关系,应该如何理解.

回复
阅读 5.7k
2 个回答

这个说法是不正确的,
如果只是你题中的优点,那么,很明显,二叉树更适合,
但是在使用中,二叉树是不稳定的,有几率变成单链表,所以还有平衡二叉树。
而且随着数据量的增大,查找效率是指数降低,因为二叉树的查找效率跟它的层级成正比。
B-树和B+树都是在二叉树的基础上(但本身并非二叉树)改良而来,是一种平衡策略。
B+树经过父节点缩小范围,然后通过叶子节点遍历查找,并非效率最高,
但是,由于数据库或文件操作设计IO,这样大大减少了IO,所以速度快。
以上是范围查找,对于点查找,hash更合适。

这句话的理解确实和B+树的原理有着密切的联系。
来看一张简单的B+树示意图,该图有一个根节点,剩下的只有叶子结点(没有中间结点)。
图片描述

相对于B-树来说,B+树有这样的特点:上级结点的元素会在下级结点中出现,例如图中根节点中的“1”,也会出现在第一个叶子结点中;叶子结点之间是相互连接的(这是一个双向链表的结构)。
现在假设图中的根节点存放的是主键Id,叶子结点存放的是数据项(包括主键Id,还有其他列)。现在我们要执行这样的SQL:

SELECT *
  FROM table
 WHERE id = 2426

这时候数据库就会在根节点中查找id=2426,在根节点中从上往下查找,可以得出2426是在2425到2829之间,所以要到第7个叶子结点中查找就可以找到id=2426的数据。这就是B+树中键值的查找方式,可以看到要找到id=2426的数据,总共只要访问B+树的两个结点,磁盘IO开销是比较小的。
当要执行这样的SQL:

SELECT *
  FROM table
 WHERE id > 407 AND id < 1618

这就涉及到键值范围查找的问题了,首先来看407,在根节点中处于405到809之间,所以应该到第二个叶子结点中开始找起,由于B+树的叶子结点是一个双向链表,意味着当第二个数据页406-808检索完毕后,可以直接跳到下一个叶子结点检索,直到所需数据都检索完毕。
如果想加深理解B+树的优点,可以与B-树对比理解一下。

宣传栏