Как устроено хранение ключей и значений внутри Bucket в key-value базах данных (на примере BoltDB/bbolt)?

В key-value базах данных, таких как bbolt (форк BoltDB), Bucket является основной структурой для группировки связанных ключей. Внутри бакета данные организованы с помощью B+ дерева (B+ tree).

Принцип работы B+ дерева:

1. 
   

   Сортировка ключей: Все ключи внутри одного бакета хранятся в отсортированном побайтово (лексикографически) порядке. Это позволяет очень быстро выполнять как поиск по точному ключу, так и сканирование диапазона ключей (range scan).

   
   

2. Структура узлов: Дерево состоит из внутренних узлов (internal nodes) и листовых узлов (leaf nodes).

   • Листовые узлы содержат непосредственно пары ключ-значение.
   • Внутренние узлы содержат ключи-разделители и ссылки на дочерние узлы.
3. 
   

   Эффективность: Такая структура оптимизирована для работы с диском. Данные, которые часто запрашиваются вместе (соседние ключи), физически находятся рядом, что минимизирует количество операций чтения с диска.

   
   

Визуальное представление:

После выполнения команд:

bucket.Put([]byte("user:10"), []byte("Alice"))
bucket.Put([]byte("user:05"), []byte("Bob"))
bucket.Put([]byte("config:1"), []byte("true"))

Внутренняя структура будет выглядеть примерно так (упрощенно):

// Листовой узел B+ дерева
["config:1"] -> "true"
["user:05"]  -> "Bob"
["user:10"]  -> "Alice"

Ключевые характеристики:

• Транзакционность: Все операции чтения и записи в bbolt являются транзакционными (ACID).
• Уникальность ключей: Ключи должны быть уникальны в пределах одного бакета.
• Вложенность: Бакеты могут быть вложены друг в друга, создавая иерархическую структуру данных.