Является ли это ошибкой в ​​6-м издании Концепции системы баз данных - рис. 11.11. Запрос B + -дерева. -Процедура printAll (значение V)?

Question

В разделе «Концепции системы баз данных», 6 ^th edition, глава 11, на «Рис. 11.11 Запрос B + -дерева» есть procedure printAll(value V). Используется для печати всех записей со значением ключа поиска V (могут быть дубликаты). Он вызывает find(V), который возвращает первый листовой узел с ключом V и первый индекс i в этом листе, который имеет этот ключ.

Почему не 'Если код не включает Set i = 1, когда i > number of keys in L?

процедура printAll ( значение V )
/ * печатает все записи со значением ключа поиска V * /
Set done = false;
Set ( L, i ) = find ( V );
если (( L, i ) is null) return
repeat
повтор
Распечатать запись указано LP _i
Set i = i + 1
до ( i > количество клавиш в L или LK _i > V )
if ( i > количество ключей в L )
тогда L = LP _n // Не нужно устанавливать i на 1?
else Set done = true;
unti l (выполнено или L равно нулю)

Answer 1

Вы абсолютно правы. i необходимо сбросить до 1 при переходе к следующему листу в дереве B +.

Это также не исправлено в "Errata and Updates For Database System Concepts, 6 ^th Edition "

На github есть реализация C ++ , вдохновленная этой книгой, которая выполняет reset 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;
        }
    }
}