1

在 Database System Concepts，第 6版，第 11 章，“图 11.11 查询 B+-树”中，有一个procedure printAll(value V). 它用于打印搜索键值为V的所有记录（可以有重复）。它调用，它返回具有键Vfind(V)的第一个叶节点，以及该叶中具有该键的第一个索引i。

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

procedure printAll( value V )
    /* 打印搜索键值为V的所有记录*/
    Set done = false;
    设置 ( L,i ) = 查找( V );
    if (( L,i ) 为空) return
    repeat
        repeat打印LP i
            指向的记录             Set i = i + 1 until ( i > L中的键数或L.K i > V ) if ( i > 中的键数

       
        L )
            then L = LP n // 不需要将i设置为 1？
            否则设置完成=真；
    直到（完成或L为空）

4

1 回答 1

1

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

在“数据库系统概念的勘误和更新，第 6版”中也没有更正它

受本书启发，github 上有一个 C++ 实现，它确实将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;
        }
    }
}
于 2020-06-17T08:48:04.523 回答