Операция записи в дерево

Чтение из дерева — это просто спуск. Но запись (INSERT/UPDATE) гораздо сложнее. База должна не просто записать данные, но и перестроить дерево так, чтобы оно осталось сбалансированным.

Поскольку каждый узел дерева имеет фиксированный размер (страницу диска 4-8 КБ), в него нельзя впихивать ключи бесконечно. Когда место заканчивается, происходит разделение узла (в англ литературе это называется node split):

1. Разрыв: Узел делится пополам. Создается новая страница на диске.
2. Переезд: Половина ключей переезжает в новый узел.
3. Эффект домино: Средний ключ выталкивается наверх в родительский узел. Если родитель тоже полон — он тоже рвется. В редких случаях дерево может вырасти на один уровень вверх прямо до самого корня.

Разделение узла — это долго. Нужно создать новые страницы, обновить указатели в старых, прописать ссылки в родителе. А что, если в середине этого процесса выключится свет? Дерево окажется в «разорванном» состоянии и индекс будет навсегда испорчен.

Чтобы этого не случилось, все СУБД используют WAL (Журнал упреждающей записи):

• Сначала Лог: Любое изменение сначала записывается в текстовый файл-лог (Append-only). Это очень быстро, потому что диск просто дописывает строку в конец.
• Потом Дерево: Только после того, как лог сохранен на диске, база начинает перестраивать само B+ дерево в памяти и на диске.
• Восстановление: Если сервер упал во время сплита, при перезагрузке база прочитает WAL и «доиграет» все незавершенные операции. Твои данные в безопасности.