Предисловие

Привет читателям Хабра! Я действующий backend Java-разработчик, примерно полтора года назад в моем информационном поле все чаще стали мелькать заголовки, подкасты и лестные отзывы о языке программирования Rust, и я решил погрузиться в этот волшебный мир Zero Cost Abstraction, отсутствия NullPointer и safety blazing fast программирования. После изучения синтаксиса, чтения The Rust Book, прорешивания rustlings и имея за плечами опыт изучения Java, стало очевидно, что для лучшего знакомства нужно как можно больше использовать язык на практике, а именно в более или менее настоящих проектах. Этой статьей я хочу начать цикл, в котором расскажу о своих пет-проектах. Мотивацией для данной инициативы служит желание глубже понять, через попытку объяснить, получить критическую оценку и, может быть, найти единомышленников.

Пару месяцев назад, листая предложенные товары на одном синем маркетплейсе, мне на глаза попалась книга Эдварда Сьоре “Проектирование и реализация систем управления базами данных”. Почитав отзывы о книге и имея давнее желание глубже понять устройство реляционных баз данных, на следующий день, книга была у меня.

Немного о книге:

Я не буду подробно описывать содержание и решения, не касающиеся темы данной статьи. Автор последовательно проводит читателя через все слои типичной базы данных - от того, как данные физически сохраняются на диске, до того, как выполняется ваш SQL-запрос, подробно описывая все внутренние компоненты:

Управление дисками и файлами
Управление памятью и кэшированием
Управление транзакциями, восстановлением и конкурентностью
Управлениями записью и метаданными
Обработка запросов, синтаксический анализ и планирование

После прочтения с уверенностью могу посоветовать данную книгу всем тем, кто хочет начать погружение в разработку СУБД.

В оригинале примеры кода приведены на Java, но как упоминалось выше, одной из целей было попробовать Rust в боевом проекте, и, как мне кажется, написание хоть и простой, но системы управления базы данных - это то, где все преимущества Rust (скорость, безопасная конкурентность, проверки на этапе компиляции и т. д.) показывают себя лучше всего.

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

Введение

В этой статье я хочу осветить только маленький кусочек из всей информации представленной в книге, а именно реализацию B+Tree индекса, хранящегося на диске. Примеры кода, приведенного в статье, зависят от более низкоуровневых функций для работы с диском, буферами и транзакциями, я постараюсь описать их общий принцип работы, но могу опустить некоторые детали, на этот случай будут указаны крейты и файлы, где представлен тот или иной функционал. Также, для разъяснения структуры и логики проекта можно прибегнуть к ИИ-агентам.

Немного теории

Перед погружением в реализацию хотелось бы немного рассказать, что из себя представляет B+ дерево.

B+ дерево - это сбалансированное n-арное дерево, являющееся модификацией B-дерева. Оно состоит из корня, внутренних узлов и листьев, корень может быть либо листом, либо узлом с двумя и более потомками.

Главное отличие от B-дерева в том, что все ключи хранятся только в листьях, а внутренние узлы служат исключительно указателями. Листья имеют ссылку на соседа, позволяющую быстро обходить дерево в порядке возрастания ключей, и ссылки на данные.

Структура

Корневой узел (Root)

Верхушка дерева. Содержит ключи и ссылки на дочерние узлы. Если дерево маленькое, корень может сам быть листом.

Внутренние узлы

Содержат только копии ключей для маршрутизации. Каждый ключ указывает на дочерний узел с диапазоном значений.

Важно: Ключи во внутренних узлах повторяются в листьях (это главное отличие от обычного B-дерева).

Листовые узлы

Содержат полные записи (строки таблицы) или ссылки (RID) на эти записи. Все листья связаны между собой в двусвязный список (каждый лист имеет указатель на следующий и предыдущий).

Каждый узел B+ дерева(будь то корень, внутренний узел или лист) физически занимает ровно одну страницу (обычно в базах данных это 4 или 8Kb). Если узел не заполнен до конца, оставшееся место в странице пустует (это называется внутренняя фрагментация).

Структура на диске

В книге индекс представлен двумя физически отдельными файлами - idxname+“leaf” и idxname+“dir”. Формат страницы жёсткий: flag (int) + numrecs (int) + N слотов фиксированного размера. Строковые поля всегда занимают максимальную длину схемы.

В моей реализации используется один файл на индекс. Блоки различаются тегом (METADATA/NODE/LEAF/OVERFLOW) в едином enum исходный код. Значения ключа кодируются с реальной длиной, а не паддингом до максимума - экономия места для varchar.

Так же я решил уйти от рекурсивного кода при работе с деревом, из-за этого пришлось хранить указатель на родителя в страницах.

#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum BTreePage {
    Metadata {
        root: i32,
    },
    Node {
        parent: i32,
        children: Vec<BTreePointer>,
        next: i32,
    },
    Leaf {
        parent: i32,
        values: Vec<BTreeEntry>,
        next: i32,
    },
    Overflow {
        rids: Vec<RID>,
        next: i32,
    },
}

Давайте пройдемся по всем вариантам

Metadata

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

Node

Внутренний узел дерева, содержит ссылку на родителя (значение 0 означает, что узел является корневым), ссылки на дочерние узлы и ссылку на следующий внутренний узел.

Ссылки представлены отдельной структурой:

#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct BTreePointer {
    pub(crate) value: Value,
    pub(crate) block_num: i32,
}

Value - enum описывающий доступные типы БД:

#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Clone)]
pub enum Value {
    Integer(i32),
    Varchar(String),
}

Leaf

Листовой узел дерева, содержит номера блока родителя (0 для корневого листа), значения и ссылку на следующий узел.

Структура значения, хранимого в листе:

#[derive(Clone, Debug)]
pub(crate) struct BTreeEntry {
    pub(crate) value: Value,
    pub(crate) rid: Vec<RID>,
    pub(crate) overflow: i32,
}

Значения, в свою очередь, представляют собой ключ, массив указателей RID и номер блока переполнения.

RID - простой указатель на номер блока в файле таблицы и позиция строки на странице:

#[derive(Debug, Clone, Hash, PartialEq, Eq)]
pub struct RID(i32, i32);

Overflow

Страница переполнения, нужна на случай, если значения ключа не влезают на основную страницу листа. Содержит массив значений и номер блока следующего листа.

Запись и чтение страниц

Страницы хранятся на диске в виде последовательности байт, есть 2 метода для чтения страницы из файла и записи.

Чтение реализовано в методе read(tx: &Transaction, block: &BlockId), первый байт хранит тип страницы, дальше идут основные данные.

const METADATA: u8 = 1;
const NODE: u8 = 2;
const LEAF: u8 = 3;
const OVERFLOW: u8 = 4;

impl BTreePage {
    pub(crate) fn read(tx: &Transaction, block: &BlockId) -> DbResult<Self> {
        tx.pin(block)?;
        let mut offset = 0;
        let page_type = tx.get_u8(block, offset)?;
        offset += U8_SIZE;
        let page = match page_type {
            METADATA => {
                offset += U8_SIZE;
                let root = tx.get_i32(block, offset)?;
                Ok(Self::Metadata { root })
            }
            NODE => {
                let parent = tx.get_i32(block, offset)?;
                offset += I32_SIZE;
                let len = tx.get_i32(block, offset)? as usize;
                offset += I32_SIZE;
                let children = read_pointers(tx, block, offset, len)?;
                let offset = tx.block_size() as usize - NEXT_SIZE;
                let next = tx.get_i32(block, offset)?;
                Ok(Self::Node {
                    parent,
                    children,
                    next,
                })
            }
            LEAF => {
                let parent = tx.get_i32(block, offset)?;
                offset += I32_SIZE;
                let len = tx.get_i32(block, offset)? as usize;
                offset += I32_SIZE;
                let children = read_entries(tx, block, offset, len)?;
                let offset = tx.block_size() as usize - I32_SIZE;
                let next = tx.get_i32(block, offset)?;
                Ok(Self::Leaf {
                    parent,
                    values: children,
                    next,
                })
            }
            OVERFLOW => {
                let next = tx.get_i32(block, offset)?;
                offset += NEXT_SIZE;
                let len = tx.get_i32(block, offset)? as usize;
                offset += LEN_SIZE;
                let mut rids = Vec::with_capacity(len);
                for _ in 0..len {
                    let block_num = tx.get_i32(block, offset)?;
                    offset += POINTER_SIZE;
                    let slot = tx.get_i32(block, offset)?;
                    offset += POINTER_SIZE;
                    rids.push(RID::new(block_num, slot));
                }
                Ok(Self::Overflow { rids, next })
            }
            _ => Err(DbError::other("invalid page type")),
        };
        tx.unpin(block)?;
        page
    }
}

Запись представляет собой обратный процесс:

impl BTreePage {
    pub(crate) fn write(&self, block: &BlockId, tx: &Transaction) -> DbResult<()> {
        tx.pin(block)?;
        match self {
            Self::Metadata { root } => {
                let mut offset = 0;
                tx.set_u8(block, offset, METADATA, true)?;
                offset += U8_SIZE;
                offset += U8_SIZE;
                tx.set_i32(block, offset, *root, true)?;
            }
            Self::Node {
                parent,
                children,
                next,
            } => {
                let mut offset = 0;
                tx.set_u8(block, offset, NODE, true)?;
                offset += U8_SIZE;
                tx.set_i32(block, offset, *parent, true)?;
                offset += I32_SIZE;
                write_pointers(tx, block, children, offset)?;
                let offset = tx.block_size() as usize - NEXT_SIZE;
                tx.set_i32(block, offset, *next, true)?;
            }
            Self::Leaf {
                parent,
                values: children,
                next,
            } => {
                let mut offset = 0;
                tx.set_u8(block, offset, LEAF, true)?;
                offset += U8_SIZE;
                tx.set_i32(block, offset, *parent, true)?;
                offset += I32_SIZE;
                write_entries(tx, block, children, offset)?;
                let offset = tx.block_size() as usize - I32_SIZE;
                tx.set_i32(block, offset, *next, true)?;
            }
            Self::Overflow { rids, next } => {
                let mut offset = 0;
                tx.set_u8(block, offset, OVERFLOW, true)?;
                offset += U8_SIZE;
                tx.set_i32(block, offset, *next, true)?;
                offset += NEXT_SIZE;
                tx.set_i32(block, offset, rids.len() as i32, true)?;
                offset += LEN_SIZE;
                for rid in rids {
                    tx.set_i32(block, offset, rid.block_num(), true)?;
                    offset += POINTER_SIZE;
                    tx.set_i32(block, offset, rid.slot(), true)?;
                    offset += POINTER_SIZE;
                }
            }
        }
        tx.unpin(block)
    }
}

Запись и чтение происходит через структуру транзакции, внутри довольно сложная логика по закреплению/откреплению буферов с конкурентным доступом, записью WAL и работой с диском. Сейчас можно считать, что мы просто побайтово читаем и пишем значения в блок файла.

Основные операции

Вставка

Вставка - самая нетривиальная операция: помимо добавления пары (ключ, RID) в лист может потребоваться каскадное разбиение страниц вверх по дереву, вплоть до создания нового корня.

Спуск к нужному листу - при вставке, поиске и удалении - устроен одинаково: начинаем с блока 0 (страница метаданных), читаем оттуда номер текущего корня, а дальше на каждом внутреннем узле находим дочерний блок, диапазон которого содержит наш ключ:

pub(crate) fn pointer_index(values: &[BTreePointer], value: &Value) -> usize {
    values
        .binary_search_by(|k| k.value.cmp(value))
        .unwrap_or_else(|x| if x == 0 { 0 } else { x - 1 })
}

В каждом указателе (BTreePointer) хранится не диапазон, а только минимальный ключ поддерева, поэтому нужен не индекс точного совпадения, а индекс последнего указателя, чей ключ не превышает искомый - отсюда x - 1 в случае неудачного поиска (x - позиция, в которую следовало бы вставить ключ, чтобы сохранить сортировку).

Добравшись до листа, вставляем пару в отсортированный по ключу вектор записей:

fn leaf_insert_rid(
    &self,
    children: &mut Vec<BTreeEntry>,
    key: Value,
    rid: RID,
    entry_budget: usize,
) -> DbResult<()> {
    match children.binary_search_by(|kv| kv.value.cmp(&key)) {
        Ok(idx) => {
            if children[idx].size() + 2 * POINTER_SIZE <= entry_budget {
                children[idx].rid.push(rid);
            } else {
                let head = self.append_overflow(children[idx].overflow, rid)?;
                children[idx].overflow = head;
            }
        }
        Err(idx) => {
            let base = TYPE_SIZE + key.size() + OVERFLOW_SIZE + LEN_SIZE;
            let entry = if base + 2 * POINTER_SIZE <= entry_budget {
                BTreeEntry {
                    value: key,
                    rid: vec![rid],
                    overflow: -1,
                }
            } else {
                let head = self.append_overflow(-1, rid)?;
                BTreeEntry {
                    value: key,
                    rid: vec![],
                    overflow: head,
                }
            };
            children.insert(idx, entry);
        }
    }
    Ok(())
}

Здесь два сценария:

Ключ уже есть в листе (дубликат, например индекс по неуникальному полю). Если добавление ещё одного RID не выведет запись за границу отведённого на лист места (entry_budget), новый RID просто дописывается в вектор values[idx].rid. Иначе он уходит в страницу переполнения (overflow).
Ключа ещё нет. Если новая запись целиком (ключ плюс место минимум под один RID) влезает в свободное место - создаём обычную запись прямо в листе. Если нет (например, очень длинный VARCHAR) - запись создаётся сразу без RID в основном листе, а сам RID сразу уходит в overflow.

Работа с переполнением инкапсулирована в append_overflow: если голова цепочки уже существует и в неё влезает ещё один RID, значение дописывается в существующую страницу, иначе создаётся новая страница в начало цепочки:

fn append_overflow(&self, head: i32, rid: RID) -> DbResult<i32> {
    let block_size = self.tx.block_size() as usize;
    if head != -1 {
        let block = BlockId::new(&self.index_name, head);
        if let BTreePage::Overflow { mut rids, next } = BTreePage::read(&self.tx, &block)?
            && overflow_size(rids.len() + 1) <= block_size
        {
            rids.push(rid);
            BTreePage::Overflow { rids, next }.write(&block, &self.tx)?;
            return Ok(head);
        }
    }
    let new_block = self.tx.append(&self.index_name)?;
    BTreePage::Overflow {
        rids: vec![rid],
        next: head,
    }
        .write(&new_block, &self.tx)?;
    Ok(new_block.num)
}

После вставки в лист проверяется итоговый размер страницы. Если он превысил размер блока - лист нужно разбить пополам split_entries, а получившуюся пару (левая половина остаётся на месте, правая уезжает в новый блок) как-то встроить в дерево. Вся эта логика - спуск, вставка, разбиение и подъём разбиения вверх по дереву - реализована одним циклом:

fn insert(&self, key: Value, rid: RID) -> DbResult<()> {
    // Текущий блок
    let mut block = BlockId::new(&self.index_name, 0);
    // Текущая страница
    let mut page = BTreePage::read(&self.tx, &block)?;
    // Разделение (ключ, номер блока)
    let mut split = None::<(Value, i32, Value, i32)>;
    // Размер блока 
    let block_size = self.tx.block_size() as usize;
    // Создавать ли новый корень
    let mut new_root = None::<i32>;

    loop {
        match page {
            // Метаданные
            BTreePage::Metadata { root } => {
                // Если есть новый корень перезаписываем указатель
                // и выходим из цикла
                if let Some(root) = new_root.take() {
                    let page = BTreePage::Metadata { root };
                    page.write(&block, &self.tx)?;
                    break;
                }
                // Заменяем указатель на блок новым значением
                block = BlockId::new(&self.index_name, root);
                // Вычитываем корень
                page = BTreePage::read(&self.tx, &block)?;
            }
            BTreePage::Node {
                parent,
                mut children,
                next,
            } => {
                // Дочерний блок разделился
                if let Some((left_key, left_block, right_key, right_block)) = split.take() {
                    update_pointer(&mut children, left_block, left_key);
                    insert_pointer(
                        &mut children,
                        BTreePointer {
                            value: right_key,
                            block_num: right_block,
                        },
                    );
                    // Новое значение вместилось, записываем узел, выходим из цикла
                    if node_size(&children) <= block_size {
                        let page = BTreePage::Node {
                            parent,
                            children,
                            next,
                        };
                        page.write(&block, &self.tx)?;
                        break;
                    }
                    // Процесс разделения узла
                    let (children, right_children) = split_pointers(children, block_size);
                    let left_key = children[0].value.clone();
                    let right_key = right_children[0].value.clone();

                    // Узел является корневым, создаем новый корень
                    if parent == 0 {
                        let parent_block = self.tx.append(&self.index_name)?;
                        new_root = Some(parent_block.num);
                        let right_block = self.tx.append(&self.index_name)?;
                        self.rewrite_parent(&right_children, right_block.num)?;
                        let left = BTreePage::Node {
                            parent: parent_block.num,
                            children,
                            next: right_block.num,
                        };
                        let right = BTreePage::Node {
                            parent: parent_block.num,
                            children: right_children,
                            next,
                        };
                        let root = BTreePage::Node {
                            parent: 0,
                            children: vec![
                                BTreePointer {
                                    value: left_key,
                                    block_num: block.num,
                                },
                                BTreePointer {
                                    value: right_key,
                                    block_num: right_block.num,
                                },
                            ],
                            next: -1,
                        };
                        root.write(&parent_block, &self.tx)?;
                        left.write(&block, &self.tx)?;
                        right.write(&right_block, &self.tx)?;
                        block = BlockId::new(&self.index_name, 0);
                        page = BTreePage::Metadata {
                            root: parent_block.num,
                        };
                    // Разбиваем текущий, не корневой узел на два
                    } else {
                        let right_block = self.tx.append(&self.index_name)?;
                        self.rewrite_parent(&right_children, right_block.num)?;
                        let left = BTreePage::Node {
                            parent,
                            children,
                            next: right_block.num,
                        };
                        let right = BTreePage::Node {
                            parent,
                            children: right_children,
                            next,
                        };
                        left.write(&block, &self.tx)?;
                        right.write(&right_block, &self.tx)?;
                        split = Some((left_key, block.num, right_key, right_block.num));
                        block = BlockId::new(&self.index_name, parent);
                        page = BTreePage::read(&self.tx, &block)?;
                    }
                // Ищем индекс листа 
                } else {
                    let idx = pointer_index(&children, &key);
                    let Some(child_offset) = children.get(idx) else {
                        return Err(DbError::other("empty node's leafs"));
                    };
                    block = BlockId::new(&self.index_name, child_offset.block_num);
                    page = BTreePage::read(&self.tx, &block)?;
                }
            }
            BTreePage::Leaf {
                parent,
                values: mut children,
                next,
            } => {
                let entry_budget = block_size - leaf_header_size();
                let min_entry = TYPE_SIZE + key.size() + OVERFLOW_SIZE + LEN_SIZE;
                if min_entry > entry_budget {
                    return Err(DbError::MaxSize(entry_budget, min_entry));
                }
                self.leaf_insert_rid(&mut children, key.clone(), rid.clone(), entry_budget)?;
                if leaf_size(&children) <= block_size {
                    let page = BTreePage::Leaf {
                        parent,
                        values: children,
                        next,
                    };
                    page.write(&block, &self.tx)?;
                    break;
                }
                let (children, right_children) = split_entries(children, block_size);
                let left_key = children[0].value.clone();
                let right_key = right_children[0].value.clone();
                if parent == 0 {
                    let parent_block = self.tx.append(&self.index_name)?;
                    let right_block = self.tx.append(&self.index_name)?;
                    let left = BTreePage::Leaf {
                        parent: parent_block.num,
                        values: children,
                        next: right_block.num,
                    };
                    let right = BTreePage::Leaf {
                        parent: parent_block.num,
                        values: right_children,
                        next,
                    };
                    let root = BTreePage::Node {
                        parent: 0,
                        children: vec![
                            BTreePointer {
                                value: left_key,
                                block_num: block.num,
                            },
                            BTreePointer {
                                value: right_key,
                                block_num: right_block.num,
                            },
                        ],
                        next: -1,
                    };
                    root.write(&parent_block, &self.tx)?;
                    left.write(&block, &self.tx)?;
                    right.write(&right_block, &self.tx)?;
                    new_root = Some(parent_block.num);
                    block = BlockId::new(&self.index_name, 0);
                    page = BTreePage::Metadata {
                        root: parent_block.num,
                    };
                } else {
                    let right_block = self.tx.append(&self.index_name)?;
                    let left = BTreePage::Leaf {
                        parent,
                        values: children,
                        next: right_block.num,
                    };
                    let right = BTreePage::Leaf {
                        parent,
                        values: right_children,
                        next,
                    };
                    left.write(&block, &self.tx)?;
                    right.write(&right_block, &self.tx)?;
                    split = Some((left_key, block.num, right_key, right_block.num));
                    block = BlockId::new(&self.index_name, parent);
                    page = BTreePage::read(&self.tx, &block)?;
                }
            }
            BTreePage::Overflow { .. } => {
                return Err(DbError::other("unexpected overflow page during insert"));
            }
        }
    }
    Ok(())
}

Коротко о происходящем:

Пока в переменной split ничего нет, мы просто идем вниз по дереву (Node → следующий Node/Leaf), до того, как не найдём подходящий лист.
Если после вставки лист (а на следующих итерациях - внутренний узел) переполнился, вызывается split_entries/split_pointers, а описание разбиения (левый ключ и блок, правый ключ и блок) кладётся в split, и цикл переходит к родителю.
На уровне родителя, если в split что-то лежит, сначала через update_pointer обновляется сепаратор для левого блока - его минимальный ключ мог измениться, например, при вставке значения меньше всех уже имеющихся, а затем через insert_pointer добавляется сепаратор для нового правого блока.
Если после этого сам родитель переполняется, он тоже разбивается, а информация о разбиении поднимается ещё на уровень выше - и так далее, пока какой-то из узлов не поглотит изменение без переполнения.
Отдельный случай - переполнение корня (parent == 0). Тогда выделяются два новых блока: новый корень и правая половина разбиваемого узла, а старый блок с содержимым корня становится левой половиной. Так высота дерева увеличивается на единицу.

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

fn rewrite_parent(&self, values: &[BTreePointer], parent: i32) -> DbResult<()> {
    for value in values {
        let block = BlockId::new(&self.index_name, value.block_num);
        match BTreePage::read(&self.tx, &block)? {
            BTreePage::Node { children, next, .. } => {
                let page = BTreePage::Node {
                    parent,
                    children,
                    next,
                };
                page.write(&block, &self.tx)?;
            }
            BTreePage::Leaf { values, next, .. } => {
                let page = BTreePage::Leaf {
                    parent,
                    values,
                    next,
                };
                page.write(&block, &self.tx)?;
            }
            _ => return Err(DbError::other("unexpected B-Tree index page type")),
        }
    }
    Ok(())
}

Разбиение вектора указателей/записей пополам делает пара функций: они делят вектор по количеству элементов, а затем подстраивают границу так, чтобы обе половины гарантированно уместились на странице - это особенно важно для VARCHAR-ключей переменной длины, где деление ровно пополам по количеству элементов не гарантирует деление пополам по байтам:

pub(crate) fn split_pointers(
    mut values: Vec<BTreePointer>,
    block_size: usize,
) -> (Vec<BTreePointer>, Vec<BTreePointer>) {
    let mid = values.len() / 2;
    let mut right = values.split_off(mid);
    let mut size = node_size(&values);
    while size > block_size {
        let value = right.remove(0);
        size -= TYPE_SIZE + value.value.size() + POINTER_SIZE;
        values.push(value);
    }
    (values, right)
}

split_entries для листьев устроен аналогично, только оперирует BTreeEntry и учитывает размер под RID.

Поиск

Поиск по индексу всегда идёт по точному совпадению ключа:

fn before_first(&mut self, key: Value) -> DbResult<()> {
    let mut block = BlockId::new(&self.index_name, 0);
    let mut page = BTreePage::read(&self.tx, &block)?;
    loop {
        match page {
            BTreePage::Metadata { root, .. } => {
                block = BlockId::new(&self.index_name, root);
                page = BTreePage::read(&self.tx, &block)?;
            }
            BTreePage::Node { children, .. } => {
                let idx = pointer_index(&children, &key);
                block = BlockId::new(&self.index_name, children[idx].block_num);
                page = BTreePage::read(&self.tx, &block)?;
            }
            BTreePage::Leaf { values, .. } => {
                match values.binary_search_by(|v| v.value.cmp(&key)) {
                    Ok(idx) => {
                        self.position = -1;
                        self.rid = self.collect_rids(&values[idx])?;
                    }
                    Err(_) => tracing::debug!("value not found"),
                };
                return Ok(());
            }
            BTreePage::Overflow { .. } => {
                return Err(DbError::other("unexpected overflow page during descent"));
            }
        }
    }
}

Если ключ найден, курсор position сбрасывается на -1, а все связанные с ключом RID собираются в self.rid - включая те, что “разъехались” по цепочке overflow-страниц:

fn collect_rids(&self, entry: &BTreeEntry) -> DbResult<Vec<RID>> {
    let mut rids = entry.rid.clone();
    let mut next = entry.overflow;
    while next != -1 {
        let block = BlockId::new(&self.index_name, next);
        match BTreePage::read(&self.tx, &block)? {
            BTreePage::Overflow {
                rids: chunk,
                next: chunk_next,
            } => {
                rids.extend(chunk);
                next = chunk_next;
            }
            _ => return Err(DbError::other("expected overflow page")),
        }
    }
    Ok(rids)
}

Дальше - обычный курсорный интерфейс:

fn next(&mut self) -> DbResult<bool> {
    self.position += 1;
    Ok((self.position as usize) < self.rid.len())
}

fn get_data_rid(&self) -> DbResult<RID> {
    Ok(self.rid[self.position as usize].clone())
}

next() просто продвигает позицию по уже собранному в памяти вектору rid, а get_data_rid() возвращает текущее значение. Если ключ не был найден в листе, self.rid остаётся пустым, и первый же вызов next() вернёт false - вызывающий код (например, IndexScan) увидит это просто как “совпадений нет”, без отдельной ошибки.

Асимптотика - O(log n) на спуск по дереву плюс O(k), где k - количество совпадений (включая overflow-цепочку), на их сбор в память.

Удаление

Удаление устроено симметрично поиску: тот же спуск по дереву до листа, binary_search по ключу, а дальше - попытка найти конкретный RID среди значений записи, и если не нашли - поискать его уже в overflow-цепочке:

fn delete(&self, key: Value, rid: RID) -> DbResult<()> {
    let mut block = BlockId::new(&self.index_name, 0);
    let mut page = BTreePage::read(&self.tx, &block)?;
    loop {
        match page {
            BTreePage::Metadata { root, .. } => {
                block = BlockId::new(&self.index_name, root);
                page = BTreePage::read(&self.tx, &block)?;
            }
            BTreePage::Node { children, .. } => {
                let idx = pointer_index(&children, &key);
                block = BlockId::new(&self.index_name, children[idx].block_num);
                page = BTreePage::read(&self.tx, &block)?;
            }
            BTreePage::Leaf {
                parent,
                mut values,
                next,
            } => {
                if let Ok(idx) = values.binary_search_by(|v| v.value.cmp(&key)) {
                    if let Some(position) = values[idx].rid.iter().position(|x| *x == rid) {
                        values[idx].rid.remove(position);
                        let page = BTreePage::Leaf {
                            parent,
                            values,
                            next,
                        };
                        page.write(&block, &self.tx)?;
                    } else {
                        self.delete_from_overflow(values[idx].overflow, &rid)?;
                    }
                }
                break;
            }
            BTreePage::Overflow { .. } => {
                return Err(DbError::other("unexpected overflow page during delete"));
            }
        }
    }
    Ok(())
}

Важный момент, отличающий эту реализацию от “полного” алгоритма удаления в классических источниках: здесь нет слияния (merge) страниц при их опустошении. Если после удаления запись или целый лист остаются пустыми, они просто остаются на своих местах - страница не удаляется, соседи не сливаются, высота дерева не уменьшается. Функционально дерево остаётся корректным (вставка и поиск продолжают работать как ни в чём не бывало), но в сценарии с интенсивными удалениями возможна внутренняя фрагментация - часть страниц будет храниться “полупустыми” или вовсе без записей.

Реализация

Само дерево используется через тонкую обёртку, реализующую общий для всех индексов движка трейт Index:

pub trait Index {
    fn before_first(&self, key: Value) -> DbResult<()>;
    fn next(&self) -> DbResult<bool>;
    fn get_data_rid(&self) -> DbResult<RID>;
    fn insert(&self, value: Value, rid: RID) -> DbResult<()>;
    fn delete(&self, value: Value, rid: RID) -> DbResult<()>;
    fn close(&self) -> DbResult<()>;
}

Все методы принимают &self, а не &mut self - так удобнее встраивать индекс в цепочки Rc<dyn Scan>, из которых собираются планы запросов (остальные сканы движка, например IndexScan, устроены так же). Но курсор поиска (position, rid) и содержимое дерева на диске всё равно изменяются при каждом вызове, поэтому вся внутренняя логика вынесена в приватную структуру BTreeIndexInner, а публичная BTreeIndex даёт к ней доступ через RefCell:

pub(crate) struct BTreeIndex(RefCell<BTreeIndexInner>);

impl Index for BTreeIndex {
    fn before_first(&self, key: Value) -> DbResult<()> {
        let mut inner = self.0.borrow_mut();
        inner.before_first(key)
    }

    fn insert(&self, key: Value, rid: RID) -> DbResult<()> {
        let inner = self.0.borrow();
        inner.insert(key, rid)
    }

    // next, get_data_rid, delete, close - аналогично
}

Это классический для Rust паттерн внутренней мутабельности (interior mutability): раз движок запросов однопоточный, заимствование в рантайме через RefCell безопасно и не требует дополнительных блокировок сверх тех, что и так удерживает Transaction на уровне блоков.

При первом обращении к ещё не созданному индексу файл инициализируется двумя блоками - страницей метаданных и пустым корневым листом:

fn create_index(tx: &Transaction, index_name: &str) -> DbResult<()> {
    let metadata_block = tx.append(index_name)?;
    let leaf_block = tx.append(index_name)?;

    let metadata = BTreePage::Metadata {
        root: leaf_block.num,
    };
    let leaf = BTreePage::Leaf {
        parent: 0,
        values: vec![],
        next: -1,
    };
    metadata.write(&metadata_block, tx)?;
    leaf.write(&leaf_block, tx)?;
    Ok(())
}

Использование выглядит примерно так:

let mut index = BTreeIndexInner::new("test_index", & tx)?;
for i in 0..1000 {
    index.insert(Value::Integer(i), RID::new(i, i))?;
}

index.before_first(Value::Integer(42))?;
while index.next()? {
    let rid = index.get_data_rid()?;
    // ... читаем строку таблицы по rid
}

Итог

В этой статье я постарался разобрать реализацию on-disk B+ дерева - от физического формата страницы на диске до алгоритмов вставки, поиска и удаления.

Буду рад, если статья окажется полезной тем, кто тоже решит написать свою игрушечную СУБД или просто интересуется, как устроены индексы внутри. Как обычно, весь код - на GitHub, issues и PR приветствуются.

Вслед за Эдвардом Сьоре, или как я писал свою реализацию on disk B+Tree-индекса на Rust