Своя СУБД на Rust · урок 4: B+Tree индекс

Кому это. К этому уроку у тебя есть три нижних слоя движка на Rust. В уроке 1 появилась страница Page и DiskManager поверх std::fs::File, в уроке 2 над диском встал буферный пул, где pin это владение PageGuard, а unpin делает Drop. В уроке 3 поверх пула выросла куча: таблица как набор страниц, строка адресуется стабильным Rid, seq scan обходит всё. Но у кучи есть одна большая дыра, и сегодня мы её закрываем.

Зачем. Найти строку по ключу в куче можно только одним способом: прочитать всю таблицу и сравнить каждую строку. На миллионе строк один SELECT ... WHERE id = 42 поднимает с диска всю таблицу. Нужна структура, которая по ключу приводит к Rid за считанные обращения к диску и умеет отдавать ключи по порядку для диапазонных запросов. Эта структура это B+Tree.

Зачем именно Rust. Деревья в Rust пользуются дурной славой. Каждый, кто пробовал написать двусвязный список или дерево с указателями на родителя, помнит драку с borrow checker и Rc<RefCell<Node>> на каждом шагу (подробно об этом в уроке про связные списки). Дисковый B+Tree обходит эту драку целиком, и в этом главная мысль урока. Узел здесь не объект в куче процесса, а страница, на которую ссылаются по номеру PageId. Указателей между узлами нет, есть числа в байтах. Владеет страницами буферный пул, дерево только берёт их взаймы через PageGuard. А сам узел это вид над байтами страницы, обобщённый по типу ссылки: через &Page он только читает, через &mut Page или защёлку на запись ещё и пишет, и это различие проверяет компилятор, а не дисциплина.

Важно про код. Как и прежде, ты пишешь реализацию с нуля в своём крейте ourdb (только std, edition 2021, rust-version = "1.84"). Модуль урока это src/btree/ из трёх файлов: node.rs (вид на узел), mod.rs (дерево) и validate.rs (проверка инвариантов). Это самый алгоритмически плотный урок воркшопа: расщепление узла с подъёмом разделителя легко понять на картинке и легко напутать в коде на границах. Печатай руками, гоняй cargo test --test lesson_04_btree после каждого блока и обязательно поиграй с виджетом ниже.

Где мы в движке

┌────────────────────────────────────────────────┐
│  Бинарный протокол + TCP-сервер                  │  урок 11
├────────────────────────────────────────────────┤
│  Исполнитель (Volcano) + EXPLAIN                 │  урок 6
│  Планировщик, binder, парсер, лексер             │  уроки 5, 6
├────────────────────────────────────────────────┤
│  Vacuum                                          │  урок 10
│  MVCC (видимость, снимки)                        │  уроки 8, 9
│  Блокировки (2PL), менеджер транзакций           │  уроки 8, 9
│  WAL (журнал, redo, recovery)                    │  урок 7
├────────────────────────────────────────────────┤
│  B+Tree индекс                                   │  урок 4  ← мы здесь
│  Куча (slotted pages, seq scan)                  │  урок 3
├────────────────────────────────────────────────┤
│  Буферный пул (кэш страниц, вытеснение)           │  урок 2
│  DiskManager (страницы поверх файла)              │  урок 1
└────────────────────────────────────────────────┘

Индекс встаёт туда же, куда куча: поверх буферного пула. Узел дерева это страница, и за чтение, запись и выделение страниц отвечает всё тот же BufferPool из урока 2. Индекс не знает про диск напрямую, он знает только fetch_page, new_page и PageGuard. Куча отображала Rid в строку, индекс отображает ключ i64 в Rid. Связка такая: индекс по ключу находит Rid, куча по Rid отдаёт строку.

Одна деталь, которая отличает Rust-порт: у каждого индекса свой файл и свой пул. BTree получает BufferPool по значению и владеет им, как куча из урока 3 владела своим. Пул нельзя случайно разделить между двумя деревьями, потому что у него ровно один владелец.

Почему именно B+Tree

Прежде чем раскладывать байты, стоит понять, почему индекс это не обычное двоичное дерево поиска из раздела про алгоритмы.

На диске единица обмена это не ключ, а целая страница в 8 КБ. Прочитать один байт стоит столько же, сколько прочитать всю страницу. Двоичное дерево хранит по ключу в узле, и при миллионе ключей спуск к листу трогает около 20 узлов, то есть до 20 обращений к диску. Беда не в сравнениях, беда в походах на диск.

B+Tree кладёт в один узел не один ключ, а сотни, столько, сколько влезает в страницу. Это число называется fanout, и оно делает дерево низким. При fanout в несколько сотен миллионы ключей умещаются в три-четыре уровня: три-четыре прочитанные страницы вместо двадцати.

Буква «плюс» означает конкретное устройство. Значения (у нас это Rid) лежат только в листьях. Внутренние узлы хранят лишь разделители: ключи, которые говорят, в какую ветку спускаться. Отсюда два выигрыша. Внутренние узлы не тащат значения, поэтому fanout ещё выше. А листья связаны в цепочку слева направо, и диапазонный запрос (WHERE id BETWEEN 25 AND 60) спускается к первому подходящему листу и дальше бежит по цепочке, не возвращаясь наверх.

И последнее: дерево всегда сбалансировано. Все листья на одной глубине, а глубина растёт только когда расщепляется корень. Баланс держит расщепление переполненных узлов снизу вверх, без отдельного прохода ребалансировки. Поиграй: вставляй ключи и смотри, как лист переполняется и делится, как разделитель всплывает наверх и как в какой-то момент корень расщепляется и дерево становится выше.

Если повозился с виджетом, ты уже видел три вещи, которые сейчас запрограммируешь. Лист переполняется и делится на два, минимальный ключ правого листа копируется наверх как разделитель. Новые листья встают в цепочку, поэтому скан по порядку идёт слева направо. Высота растёт только при расщеплении корня. Теперь уложим это в байты.

Контракт байтов узла

Байты узла общие для всех реализаций ourdb: TS, Effect, Go и Rust пишут один и тот же формат, и файл индекса, записанный одной, читается другой. Это тот же контракт, что в TS-уроке, поэтому пройдём по нему коротко.

Узел это страница, но размечена она иначе, чем страница кучи. Слоты узлу не нужны, ему нужен компактный отсортированный массив ячеек. Заголовок узла лежит не в начале, а в special-области в конце страницы, а ячейки пакуются подряд от HEADER_SIZE (16 байт заголовка страницы из урока 1) вверх. Все числа little-endian.

Заголовок узла это 8 байт со смещения special = PAGE_SIZE - 8 = 8184:

смещение  размер  поле
0         2       node_type   u16   0 = internal, 1 = leaf
2         2       key_count   u16   число разделителей (внутр.) или ячеек (лист)
4         4       next_leaf   u32   page id следующего листа (0 = нет); только у листьев

Лист хранит отсортированные ячейки (key, rid) фиксированной длины 14 байт. Ключ знаковый i64, тот же тип INT, что в куче:

смещение  размер  поле
0         8       key        i64   ключ (знаковый)
8         4       rid_page   u32   page id кучи
12        2       rid_slot   u16   слот кучи

У внутреннего узла детей на одного больше, чем разделителей: разделитель стоит между двумя ветками. Поэтому самый левый ребёнок child0 хранится отдельным ведущим указателем, а дальше идут ячейки (separator, child) по 12 байт:

смещение            размер  поле
16                  4       child0      u32   самый левый ребёнок
20 + i*12           8       separator   i64   разделитель s_i
20 + i*12 + 8       4       child       u32   ребёнок c_(i+1)

Разделитель s_i это минимальный ключ поддерева child(i+1), а child0 держит ключи меньше s_0. Спуск по ключу K идёт в ребёнка с номером «сколько разделителей <= K»: равенство уходит вправо, туда же, куда вставка кладёт новые равные ключи. Дубликаты разрешены, поэтому range scan стартует по самому левому ребёнку, где ключ ещё может встретиться, чтобы не проскочить дубли в листьях левее.

Файл индекса самоописывающий. Page 0 это метастраница, остальные страницы это узлы:

смещение  размер  поле
0         4       magic       u32   0x42545231 ("BTR1")
4         4       root        u32   page id корня (переживает перезапуск)

При создании корнем становится лист на page 1. Когда корень расщепляется, заводится новый внутренний корень, и его номер переписывается в метастраницу.

Константы узла

Константы живут в src/btree/node.rs. В TS-треке они лежали в одном файле constants.ts, у нас каждая константа рядом с кодом, который её читает, а наружу модуль отдаёт их через pub use node::* в mod.rs.

// src/btree/node.rs
use std::ops::{Deref, DerefMut};

use crate::bytes::{get_i64, get_u16, get_u32, put_i64, put_u16, put_u32};
use crate::heap::Rid;
use crate::page::{Page, HEADER_SIZE, PAGE_SIZE};

/// Размер заголовка узла: node_type u16, key_count u16, next_leaf u32.
pub const NODE_HEADER_SIZE: usize = 8;
/// Начало special-области узла (заголовок узла).
pub const BTREE_SPECIAL: usize = PAGE_SIZE - NODE_HEADER_SIZE;
pub const NODE_INTERNAL: u16 = 0;
pub const NODE_LEAF: u16 = 1;
/// Ячейка листа: key i64 + rid.page_id u32 + rid.slot u16.
pub const LEAF_CELL_SIZE: usize = 14;
/// Ячейка внутреннего узла: separator i64 + child u32.
pub const INTERNAL_CELL_SIZE: usize = 12;
/// Смещение ведущего указателя child0 во внутреннем узле.
pub const INTERNAL_CHILD0_OFFSET: usize = HEADER_SIZE;
/// "Нет соседнего листа": page 0 это метастраница, а не лист.
pub const NO_SIBLING: u32 = 0;

const KEY_COUNT: usize = BTREE_SPECIAL + 2;
const NEXT_LEAF: usize = BTREE_SPECIAL + 4;

get_u16, put_i64 и компания это крошечные помощники из src/bytes.rs, которые ты написал в уроке 1: u16::from_le_bytes и to_le_bytes по смещению внутри страницы. Они паникуют на выходе за границы, и это верно: смещения узла вычисляются из констант, выход за страницу здесь означает баг движка, а не плохие данные.

Заметь сентинел NO_SIBLING = 0. Это безопасно: следующим листом не может быть page 0, потому что там метастраница. Магию и смещения метастраницы держит mod.rs, они нужны только дереву:

// src/btree/mod.rs
/// Магия метастраницы индекса: ASCII "BTR1".
pub const BTREE_META_MAGIC: u32 = 0x4254_5231;
pub const META_MAGIC_OFFSET: usize = 0;
pub const META_ROOT_OFFSET: usize = 4;
const META_PAGE_ID: PageId = 0;

Подчёркивание в 0x4254_5231 это просто разделитель разрядов в литерале, Rust его игнорирует. Байты 42 54 52 31 это ASCII B T R 1.

BTreeNode: вид на страницу, обобщённый по ссылке

Как Tuple в уроке 3 размечал байты кортежа, так BTreeNode размечает байты страницы как узел дерева. Ввода-вывода тут нет: читать и писать страницы на диск это дело пула. Весь тип это одна строка:

pub struct BTreeNode<P>(pub P);

Кортежная структура с одним полем P, и больше ничего: ни своего буфера, ни копии байтов. P это «что-то, через что видна страница». Методы разбиты на два блока impl с разными ограничениями:

impl<P: Deref<Target = Page>> BTreeNode<P> {
    fn buf(&self) -> &[u8] {
        &self.0.bytes()[..]
    }
    // чтение: is_leaf, key_count, key_at, route ...
}

impl<P: DerefMut<Target = Page>> BTreeNode<P> {
    fn buf_mut(&mut self) -> &mut [u8] {
        &mut self.0.bytes_mut()[..]
    }
    // запись: init_leaf, leaf_insert_at, internal_split_into ...
}

Первый блок требует от P только Deref<Target = Page>: через P можно получить &Page. Второй требует DerefMut: можно получить &mut Page. Под эти ограничения подходят три разных типа, и все три в движке реально встречаются:

Что в P	Где встречается	Что доступно
&Page	BTreeNode(&*page) при чтении под latch	только чтение
&mut Page	BTreeNode::init_leaf(&mut page) в тестах	чтение и запись
MutexGuard<'_, Page>	BTreeNode(guard.write()) в дереве	чтение и запись

Вот где Rust выигрывает у TS-версии. Там BTreeNode оборачивал Page, и ничто не мешало вызвать leafInsertAt на узле, взятом «только посмотреть»: страница изменится, а unpinPage(id, false) не пометит её грязной, и правка тихо пропадёт при вытеснении. Здесь у BTreeNode<&Page> метода leaf_insert_at просто нет: он объявлен в блоке DerefMut, а &Page этому ограничению не удовлетворяет. Попытка записать через вид на чтение это ошибка компиляции. А запись через guard.write() сама помечает кадр грязным (это устроено в уроке 2), так что «записал, но забыл сказать пулу» тоже невозможно.

Обобщение ничего не стоит во время работы. Компилятор делает мономорфизацию: для BTreeNode<&Page> и BTreeNode<MutexGuard<Page>> выйдут две копии кода, каждая со своим прямым доступом к байтам. Подробнее про ограничения на параметры в уроке про дженерики.

Почему не каст байтов в структуру

Возникает соблазн: объявить #[repr(C, packed)] struct LeafCell { key: i64, page_id: u32, slot: u16 }, привести байты страницы к &[LeafCell] и работать со срезом как с обычным массивом. Так делают в C. В Rust это unsafe, и сразу по трём причинам. Ячейка листа длиной 14 байт начинается со смещения 16 + 14 * i, то есть ключ i64 почти никогда не выровнен на 8, а ссылка на невыровненное поле packed-структуры запрещена. Порядок байт в памяти зависит от процессора, а контракт требует little-endian всегда. И наконец, из любых 14 байт вышла бы «валидная» ячейка, компилятор ничего бы не проверил. Подробнее про раскладку и выравнивание в уроке про repr и про цену такого кода в уроке про unsafe.

Вид с from_le_bytes по смещению обходится без unsafe вовсе. Чтение i64 из восьми байт компилятор на x86 и ARM сворачивает в одну загрузку плюс проверку границ среза, так что безопасный код почти не медленнее.

Методы листа

Смещения ячеек считают две свободные функции, а методы листа читают и пишут поля по этим смещениям:

fn leaf_cell(index: usize) -> usize {
    HEADER_SIZE + index * LEAF_CELL_SIZE
}

fn internal_cell(index: usize) -> usize {
    INTERNAL_CHILD0_OFFSET + 4 + index * INTERNAL_CELL_SIZE
}

impl<P: Deref<Target = Page>> BTreeNode<P> {
    fn buf(&self) -> &[u8] {
        &self.0.bytes()[..]
    }

    pub fn is_leaf(&self) -> bool {
        get_u16(self.buf(), BTREE_SPECIAL) == NODE_LEAF
    }

    pub fn key_count(&self) -> usize {
        get_u16(self.buf(), KEY_COUNT) as usize
    }

    pub fn next_leaf(&self) -> u32 {
        get_u32(self.buf(), NEXT_LEAF)
    }

    // -------- лист --------

    pub fn key_at(&self, index: usize) -> i64 {
        get_i64(self.buf(), leaf_cell(index))
    }

    pub fn rid_at(&self, index: usize) -> Rid {
        let at = leaf_cell(index);
        Rid {
            page_id: get_u32(self.buf(), at + 8),
            slot: get_u16(self.buf(), at + 12),
        }
    }

    /// Первый индекс, где key_at(index) >= key (lower_bound).
    pub fn lower_bound(&self, key: i64) -> usize {
        partition(self.key_count(), |index| self.key_at(index) < key)
    }

    /// Индекс ячейки с точным совпадением (key, rid), для удаления.
    pub fn find_leaf(&self, key: i64, rid: Rid) -> Option<usize> {
        (self.lower_bound(key)..self.key_count())
            .take_while(|&index| self.key_at(index) == key)
            .find(|&index| self.rid_at(index) == rid)
    }

    // методы внутреннего узла ниже
}

key_at читает i64 прямо из байтов: знак ключа хранится в дополнительном коде, и i64::from_le_bytes восстанавливает отрицательные ключи без всяких ухищрений. В TS-треке для этого понадобился bigint и readBigInt64LE, потому что number не держит 64-битные целые точно. В Rust нужный тип есть из коробки (про дополнительный код в уроке про целые числа).

rid_at собирает Rid из двух полей. Rid из урока 3 это Copy-структура, поэтому её возвращают по значению, никаких ссылок на байты страницы наружу не утекает.

lower_bound это lower_bound бинарным поиском. Почему не slice::partition_point из std? Он работает по срезу типизированных значений, а у нас нет &[i64]: ключи упакованы в 14-байтные ячейки вперемешку с Rid. Поэтому бинарный поиск написан один раз в виде функции над индексами, а что сравнивать, решает замыкание:

/// Бинарный поиск: число первых индексов в [0, count), для которых `before` истинно.
fn partition(count: usize, before: impl Fn(usize) -> bool) -> usize {
    let (mut low, mut high) = (0, count);
    while low < high {
        let middle = (low + high) / 2;
        if before(middle) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    low
}

Контракт тот же, что у partition_point: предикат истинен на префиксе и ложен дальше, функция возвращает длину этого префикса. На этой одной функции построены все четыре поиска узла: lower_bound в листе, route и route_leftmost во внутреннем узле. Переполнения в (low + high) / 2 не будет: count не больше пары сотен.

find_leaf ищет ячейку с точным совпадением пары (key, rid), она нужна удалению при дубликатах. Это цепочка итераторов: начни с lower_bound, иди, пока ключ равен искомому (take_while), и найди первую ячейку с нужным rid (find). Результат Option<usize>: «такой пары нет» это обычный ответ, а не ошибка.

Теперь запись. Вставка в отсортированный массив ячеек это сдвиг хвоста вправо на одну ячейку и запись новой на освободившееся место:

impl<P: DerefMut<Target = Page>> BTreeNode<P> {
    fn buf_mut(&mut self) -> &mut [u8] {
        &mut self.0.bytes_mut()[..]
    }

    /// Инициализировать страницу как пустой лист. Сначала special.
    pub fn init_leaf(page: P) -> BTreeNode<P> {
        BTreeNode::init(page, NODE_LEAF)
    }

    pub fn init_internal(page: P) -> BTreeNode<P> {
        BTreeNode::init(page, NODE_INTERNAL)
    }

    fn init(mut page: P, node_type: u16) -> BTreeNode<P> {
        page.set_special(BTREE_SPECIAL as u16);
        let mut node = BTreeNode(page);
        put_u16(node.buf_mut(), BTREE_SPECIAL, node_type);
        node.set_key_count(0);
        node.set_next_leaf(NO_SIBLING);
        node
    }

    pub fn set_key_count(&mut self, count: usize) {
        put_u16(self.buf_mut(), KEY_COUNT, count as u16);
    }

    pub fn set_next_leaf(&mut self, page_id: u32) {
        put_u32(self.buf_mut(), NEXT_LEAF, page_id);
    }

    /// Вставить ячейку листа в позицию index, сдвинув хвост вправо.
    pub fn leaf_insert_at(&mut self, index: usize, key: i64, rid: Rid) {
        let count = self.key_count();
        let at = leaf_cell(index);
        self.buf_mut()
            .copy_within(at..leaf_cell(count), leaf_cell(index + 1));
        let buf = self.buf_mut();
        put_i64(buf, at, key);
        put_u32(buf, at + 8, rid.page_id);
        put_u16(buf, at + 12, rid.slot);
        self.set_key_count(count + 1);
    }

    /// Удалить ячейку листа в позиции index, сдвинув хвост влево.
    pub fn leaf_delete_at(&mut self, index: usize) {
        let count = self.key_count();
        self.buf_mut()
            .copy_within(leaf_cell(index + 1)..leaf_cell(count), leaf_cell(index));
        self.set_key_count(count - 1);
    }

    // разрезание и методы внутреннего узла ниже
}

init принимает P по значению и возвращает готовый BTreeNode<P>. Сначала он пишет special через метод самой страницы (page.set_special работает благодаря авто-разыменованию P в &mut Page), и только потом заголовок узла в special-область. Порядок важен для читателей формата: special говорит, где искать заголовок узла.

copy_within это сдвиг байтов внутри одного среза, аналог memmove: исходный и целевой диапазоны могут пересекаться, и метод это корректно обрабатывает. В TS-треке это был buffer.copyWithin. Обрати внимание на let buf = self.buf_mut(); перед тремя put_*: одна изменяемая ссылка на байты на три записи подряд, а потом self.set_key_count берёт новую, когда buf уже не используется. Borrow checker видит, что заимствования не пересекаются, и не мешает.

Разрезание листа переносит верхнюю половину ячеек в новый правый лист:

    /// Разрезать лист: ячейки [mid..) уезжают в right. Сначала right.next = старый next,
    /// потом next = right, иначе порвётся цепочка листьев для range scan.
    pub fn leaf_split_into<Q: DerefMut<Target = Page>>(
        &mut self,
        right: &mut BTreeNode<Q>,
        right_page_id: u32,
        mid: usize,
    ) {
        let count = self.key_count();
        let cells = &self.buf()[leaf_cell(mid)..leaf_cell(count)];
        right.buf_mut()[HEADER_SIZE..HEADER_SIZE + cells.len()].copy_from_slice(cells);
        right.set_key_count(count - mid);
        right.set_next_leaf(self.next_leaf());
        self.set_key_count(mid);
        self.set_next_leaf(right_page_id);
    }

Тут два момента. Первый: right это BTreeNode<Q> со своим параметром типа. Левый узел может держать страницу через MutexGuard, правый через другой MutexGuard или &mut Page, метод работает для любой пары. Второй: cells это неизменяемый срез левой страницы, а right.buf_mut() изменяемый срез правой. Это две разные страницы, два разных владельца, поэтому взять одновременно & на одну и &mut на другую можно. Попробуй в этом методе скопировать ячейки внутри одной страницы через copy_from_slice, и компилятор остановит тебя: & и &mut на один буфер одновременно жить не могут. Для сдвига внутри страницы как раз и есть copy_within.

Порядок двух set_next_leaf выбран нарочно: правый лист сначала забирает старого соседа левого, и только потом левый указывает на правый. Переставишь строки, и правый лист получит ссылку на самого себя, а цепочка для range scan зациклится.

Методы внутреннего узла

    // в блоке impl<P: Deref<Target = Page>>

    /// child0 это ведущий указатель, остальные дети лежат в ячейках.
    pub fn child_at(&self, index: usize) -> u32 {
        if index == 0 {
            get_u32(self.buf(), INTERNAL_CHILD0_OFFSET)
        } else {
            get_u32(self.buf(), internal_cell(index - 1) + 8)
        }
    }

    /// Разделитель s_i: минимальный ключ поддерева child_at(i + 1).
    pub fn separator_at(&self, index: usize) -> i64 {
        get_i64(self.buf(), internal_cell(index))
    }

    /// Ребёнок для спуска по ключу: число разделителей с s <= key (равенство вправо).
    pub fn route(&self, key: i64) -> usize {
        partition(self.key_count(), |index| self.separator_at(index) <= key)
    }

    /// Самый левый ребёнок, который может содержать key: число s < key (начало range scan).
    pub fn route_leftmost(&self, key: i64) -> usize {
        partition(self.key_count(), |index| self.separator_at(index) < key)
    }

    // в блоке impl<P: DerefMut<Target = Page>>

    pub fn set_child_at(&mut self, index: usize, child: u32) {
        let at = if index == 0 {
            INTERNAL_CHILD0_OFFSET
        } else {
            internal_cell(index - 1) + 8
        };
        put_u32(self.buf_mut(), at, child);
    }

    /// Перезаписать разделитель (borrow обновляет разделитель родителя).
    pub fn set_separator_at(&mut self, index: usize, separator: i64) {
        put_i64(self.buf_mut(), internal_cell(index), separator);
    }

    /// Вставить разделитель в позицию index, новый правый ребёнок встаёт на index + 1.
    pub fn internal_insert_at(&mut self, index: usize, separator: i64, child: u32) {
        let count = self.key_count();
        let at = internal_cell(index);
        self.buf_mut()
            .copy_within(at..internal_cell(count), internal_cell(index + 1));
        put_i64(self.buf_mut(), at, separator);
        put_u32(self.buf_mut(), at + 8, child);
        self.set_key_count(count + 1);
    }

    /// Дописать в конец пару (separator, child).
    pub fn internal_append(&mut self, separator: i64, child: u32) {
        self.internal_insert_at(self.key_count(), separator, child);
    }

    /// Разрезать внутренний узел: s[mid] поднимается наверх и не остаётся ни в одном
    /// узле; left держит s[0..mid), right получает c[mid+1] как child0 плюс хвост.
    pub fn internal_split_into<Q: DerefMut<Target = Page>>(
        &mut self,
        right: &mut BTreeNode<Q>,
        mid: usize,
    ) -> i64 {
        let count = self.key_count();
        let promoted = self.separator_at(mid);
        right.set_child_at(0, self.child_at(mid + 1));
        for (right_index, source) in (mid + 1..count).enumerate() {
            right.set_separator_at(right_index, self.separator_at(source));
            right.set_child_at(right_index + 1, self.child_at(source + 1));
        }
        right.set_key_count(count - mid - 1);
        self.set_key_count(mid);
        promoted
    }

Здесь три места, где легко запутаться.

child_at и сдвиг на один. Детей на одного больше, чем разделителей. Ведущий child0 лежит отдельно, а ребёнок i >= 1 лежит в ячейке i - 1 рядом со своим разделителем. Этот сдвиг между нумерацией детей и разделителей самый частый источник ошибок во всём узле. Тест internal_layout_is_child0_separator_child1 ниже проверяет его по байтам.

Два маршрутизатора. route и route_leftmost отличаются одним знаком сравнения, и это вопрос корректности дубликатов. route это upper_bound: разделители с s <= key уводят вправо, поэтому при равенстве спуск идёт в правую ветку. Туда же вставка кладёт новые равные ключи, значит поиск и вставка ходят одним путём. route_leftmost при равенстве уходит влево, к самому левому листу, где может лежать дубль искомого ключа. С него стартует range scan. Поставишь не тот знак, и range scan потеряет первые совпадения, но только на дубликатах, которых в простых тестах нет.

internal_split_into. У листа разделитель копируется наверх и продолжает жить в листе. У внутреннего узла средний разделитель переезжает наверх и не остаётся ни слева, ни справа: он становится границей между половинами уровнем выше. Метод возвращает этот ключ как i64, а цикл с enumerate() раскладывает хвост в правый узел, нумеруя его ячейки с нуля. Счётчик right_index не надо вести руками, как в TS-версии.

Для удаления в этом же блоке живут ещё четыре метода (internal_prepend_child, internal_delete_at, internal_remove_first, internal_remove_last), мы покажем их в разделе про удаление.