这是数据库系统概念第 6 版中的错误吗？图 11.11 查询 B+-树。-过程 printAll(value V)？

Question

数据库系统概念，第6^版，第11章，"Figure 11.11 Querying a B+-tree."，有一个procedure printAll(value V)。用于打印搜索关键字值为V的所有记录（可以重复）。它调用 find(V)，其中 return 是具有键 V 的第一个叶节点，以及第一个索引 i那片有那把钥匙的叶子。

为什么 i > number of keys in L 时代码不包含 Set i = 1？

程序 printAll(value V)
/* 打印搜索关键字值为 V 的所有记录 */
设置 done = false;
设置 (L,i) = find(V);
if ((L,i) 为空) return
重复
重复
打印L.P_i
指向的记录设置 i = i + 1
until (i > L or 中的键数L.K_i > V)
if (i > L 中的键数)
然后 L = L.P_n / /不需要设置i为1?
else 设置 done = true;
直到（完成或L为空）

Answer 1

你完全正确。 i移动到B+树中的下一个叶子时需要重置为1。

"Errata and Updates For Database System Concepts, 6^th Edition"

中也没有更正

有一个 C++ 实现 on github，受本书启发，确实重置了 i，因为它应该是.当然，在 C++ 中索引是从零开始的：

void BPlusTree::printAll(string v) {
    //
    // B+ tree described in the book may contain duplicate keys
    // printAl prints all the records with key v
    // but here I modified it to print all records with key >= v
    //
    bool done = false;
    auto pair = find(v);
    auto p = pair.first;
    auto i = pair.second;
    if (i == -1) {  // not found
        cout << "no such record" << endl;
        return;
    }
    cout << "i is " << i << endl;
    while (!done and p != NULL) {
         // be careful with special cases, may encounter NULL pointer, size is also a problem (#pointer = #key + 1)
        for (; (i < p->_ptrs.size() && i < p->_keys.size() && v <= p->_keys[i]) or (i == p->_keys.size()); i++) {
            if (p->_ptrs[i] == NULL) {
                continue;
            }
            cout << "record: " << *reinterpret_cast<int*>(p->_ptrs[i]) << endl;
        }
        if (i >= _num_of_keys(p)) {
            p = p->_next;  // move to next leaf node
            i = 0;  // adjust i
        }
        else {
            done = true;
        }
    }
}

这是数据库系统概念第 6 版中的错误吗？图 11.11 查询 B+-树。-过程 printAll(value V)？

Is this a bug in Database System Concepts 6th edition-Figure 11.11 Querying a B+-tree.-procedure printAll(value V)?

database

algorithm

b-plus-tree