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

Question

还以书上例子来说

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 有着不可分割的关系,应该如何理解.

Answer 1

这句话的理解确实和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-树对比理解一下。

Answer 2

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