Как хранятся key-value в бакете?

Хранение key-value в бакете BoltDB

В BoltDB (и его форке bbolt) бакет (bucket) — это именованная коллекция пар ключ-значение, организованная в виде вложенных структур внутри файла базы данных. Понимание внутреннего механизма хранения критично для оптимизации производительности.

Базовая структура хранения

BoltDB использует B+дерево для каждого бакета, что обеспечивает:

• Логарифмическое время доступа O(log n)
• Сортировку ключей в лексикографическом порядке
• Эффективный диапазонный поиск (range queries)
• Минимальную фрагментацию данных

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

Физическая организация на страницах

Данные в BoltDB хранятся в страницах (pages) фиксированного размера (обычно 4KB). Существует несколько типов страниц:

// Упрощенная структура страницы (из исходного кода bbolt)
type page struct {
    id       pgid          // Идентификатор страницы
    flags    uint16        // Тип страницы: branch, leaf, meta, freelist
    count    uint16        // Количество элементов
    overflow uint32        // Количество overflow-страниц
    ptr      uintptr       // Указатель на данные
}

// Типы страниц
const (
    branchPageFlag   = 0x01  // Страница ветвления (промежуточные узлы)
    leafPageFlag     = 0x02  // Листовая страница (данные)
    metaPageFlag     = 0x04  // Мета-страница
    freelistPageFlag = 0x10  // Страница свободных страниц
)

Организация пар ключ-значение

Листовые страницы (leaf pages)

Содержат фактические данные в формате:

// Элемент листовой страницы
type leafPageElement struct {
    flags uint32      // Флаги (обычно 0)
    pos   uint32      // Смещение значения от начала элемента
    ksize uint32      // Размер ключа
    vsize uint32      // Размер значения
    // За ключом сразу следует значение в памяти
}

// В памяти располагаются так:
// | leafPageElement1 | ключ1 | значение1 | leafPageElement2 | ключ2 | значение2 | ...

Важные особенности:

• Ключи хранятся отсортированными в лексикографическом порядке
• Максимальный размер ключа — 65535 байт (ограничение uint16)
• Размер значения может быть произвольным, но большие значения используют overflow pages
• При обновлении значения создается новая запись, старая помечается как свободное место

Страницы ветвления (branch pages)

Содержат указатели на дочерние страницы:

// Элемент страницы ветвления
type branchPageElement struct {
    pos   uint32      // Смещение ключа
    ksize uint32      // Размер ключа
    pgid  uint64      // Идентификатор дочерней страницы
}

Процесс вставки данных

При вставке новой пары key-value:

1. Находим позицию в B+дереве с бинарным поиском
2. Проверяем место на целевой листовой странице
3. Если места недостаточно — разделяем страницу:

   // Псевдокод разделения страницы
   func (n *node) split(pageSize int) {
       // Создаем новую страницу
       newPage := allocateNewPage()
       
       // Перемещаем половину элементов
       splitIndex := n.count / 2
       moveElements(n, newPage, splitIndex)
       
       // Обновляем родительскую страницу
       updateParentWithNewKey(newPage.firstKey)
   }
   

4. Вставляем элемент с сохранением сортировки
5. При необходимости ребалансируем дерево

Особенности работы со значениями

Малые значения (до ~2KB) хранятся inline на листовой странице. Большие значения используют механизм overflow:

// Пример хранения большого значения
func storeLargeValue(value []byte, page *page) {
    if len(value) <= page.availableSpace() {
        // Храним inline
        storeInline(page, value)
    } else {
        // Используем overflow pages
        overflowPages := allocateOverflowPages(len(value))
        chainPages(page, overflowPages)
        storeInOverflow(overflowPages, value)
    }
}

Оптимизации производительности

1. Кэширование узлов: Часто используемые узлы кэшируются в памяти
2. Копирование при записи: Страницы не модифицируются на месте
3. Пакетные обновления: Изменения накапливаются и применяются атомарно
4. Свободное пространство: Управляется через bitmap freelist

Практический пример

package main

import (
    "fmt"
    "log"
    "github.com/etcd-io/bbolt"
)

func main() {
    // Открываем базу данных
    db, err := bbolt.Open("my.db", 0600, nil)
    if err != nil {
        log.Fatal(err)
    }
    defer db.Close()
    
    // Создаем бакет и добавляем данные
    err = db.Update(func(tx *bbolt.Tx) error {
        b, err := tx.CreateBucketIfNotExists([]byte("MyBucket"))
        if err != nil {
            return err
        }
        
        // Вставка key-value
        err = b.Put([]byte("user:1001"), []byte("John Doe"))
        err = b.Put([]byte("user:1002"), []byte("Jane Smith"))
        
        // Чтение данных
        value := b.Get([]byte("user:1001"))
        fmt.Printf("User 1001: %s\n", value)
        
        return nil
    })
}

Ключевые выводы

1. Древовидная структура: Каждый бакет — независимое B+дерево
2. Сортировка по ключам: Автоматическая лексикографическая сортировка
3. Страничная организация: Фиксированные страницы по 4KB
4. Эффективные операции: Поиск, вставка, удаление за O(log n)
5. ACID-гарантии: Атомарность через copy-on-write

Понимание этих механизмов помогает принимать обоснованные решения при проектировании структур данных и оптимизации запросов в приложениях, использующих BoltDB/bbolt.