Структуры данных на практике. Глава 10: B-деревья и деревья, эффективно использующие кэш / Хабр

«Цель вычислений — понимание, а не числа», — Ричард Хэмминг

Загадка базы данных

Вся наша база данных находилась в памяти, однако операции поиска по ней занимали 12 тысяч тактов. При миллионе показаний датчика IoT-устройства с 64 КБ кэша реализация красно-чёрного дерева оказалась слишком медленной для запросов в реальном времени.

«Давайте попробуем B-дерево», — предложил я.

«Разве они нужны не только для баз данных на дисках? — спросил лид, — У нас всё находится в памяти. Чем нам будет полезно B-дерево?»

Вопрос был вполне разумным. B-деревья были придуманы для доступа к диску; каждый узел в них — это блок диска. Однако паттерны промахов кэша выглядели подозрительно похожими на паттерны дискового ввода-вывода — всего в 100 раз, а не в 100000 раз быстрее.

В итоге мы реализовали B-дерево. Результаты удивили всех:

$ perf stat -e cache-misses,cycles ./db_query_rbtree
  Performance counter stats:
    18,500,000 cache-misses
   120,000,000 cycles

$ perf stat -e cache-misses,cycles ./db_query_btree
  Performance counter stats:
     2,800,000 cache-misses
    18,000,000 cycles

B-дерево оказалось в 6,7 раза быстрее красно-чёрного. Количество промахов кэша снизилось с 18,5 миллиона до 2,8 миллиона.

Почему? У B-дерева всего 3 уровня, а у красно-чёрного — 20 уровней. Меньше уровней = меньше промахов кэша.

Проблема двоичных деревьев

Из Главы 9 мы узнали, что двоичные деревья поиска страдают следованием по указателям. Каждый узел — это произвольное место в памяти, поэтому каждый этап обхода — это промах кэша.

Но есть и более глубокая проблема: высота деревьев.

При одном миллионе элементов:

Высота двоичного дерева: log₂(1000000) ≈ 20 уровней
Каждая операция поиска: разыменование 20 указателей
Промахи кэша: ~18-20 (почти каждый узел — это промах)

Даже если бы смогли волшебным образом сделать каждый узел удобным для поиска, то нам всё равно придётся обходить 20 уровней.

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

Решение: снизить высоту, увеличив показатель ветвления.

Что такое B-дерево?

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

Вот простой пример с порядком 4 (максимум 3 ключа на узел):

                [40|80]
               /   |   \
         [10|20] [50|60] [90|100]

Корень имеет 2 ключа (40 и 80) и 3 дочерних элемента. Каждый элемент — это тоже узел со множеством ключей.

Основные свойства:

Каждый узел содержит до M-1 ключей (M — это «порядок»).
Каждый внутренний узел имеет до M дочерних элементов.
Все листья находятся на одной глубине (дерево сбалансировано).
Ключи в каждом узле отсортированы.

Для нашей базы данных IoT мы использовали порядок 64. Это означает следующее:

Каждый узел имеет до 63 ключей.
Каждый внутренний узел имеет до 64 дочерних элементов.
Высота дерева: log₆₄(1000000) ≈ 3 уровня.

Почему B-деревья удобны для кэша

Магия B-деревьев заключается в том, что все ключи узла хранятся в памяти последовательно.

Вот структура узла, которую я использовал:

#define BTREE_ORDER 64

typedef struct btree_node {
    int num_keys;                    // 4 байта
    int keys[BTREE_ORDER - 1];       // 252 байта (63 ключа)
    void *values[BTREE_ORDER - 1];   // 504 байта
    struct btree_node *children[BTREE_ORDER];  // 512 байт
    // Итого: ~1272 байта (умещается в ~20 линий кэша)
} btree_node_t;

При доступе к узлу все 63 ключа находятся в сплошном массиве. Можно выполнять двоичный поиск по ним без следования по указателям:

int find_key(btree_node_t *node, int key) {
    // Двоичный поиск в отсортировнном массиве (удобный для кэша!)
    int left = 0, right = node->num_keys - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (node->keys[mid] == key) return mid;
        if (key < node->keys[mid]) right = mid - 1;
        else left = mid + 1;
    }
    return -1;  // Не найдено
}

Поведение кэша:

Первый доступ к узлу: 1 промах кэша (загружает узел в кэш).
Двоичный поиск внутри узла: 0 дополнительных промахов кэша (все ключи последовательные).
Итого: 1 промах кэша на один уровень дерева.

Так как уровней всего 3, на одну операцию поиска приходится всего 3 промаха кэша!

Поиск по B-дереву

void* btree_search(btree_node_t *root, int key) {
    btree_node_t *node = root;
    
    while (node) {
        // Двоичный поиск в узле (удобный для кэша)
        int i = 0;
        while (i < node->num_keys && key > node->keys[i]) {
            i++;
        }
        
        // Значение найдено?
        if (i < node->num_keys && key == node->keys[i]) {
            return node->values[i];
        }
        
        // Узел-лист?
        if (!node->children[0]) {
            return NULL;  // Не найдено
        }
        
        // Спускаемся к дочернему элементу (здесь промах кэша)
        node = node->children[i];
    }
    
    return NULL;
}

Сложность:

Высота дерева:
Поиск внутри узла:
Итого:

Промахи кэша: (по одному на уровень)

Результаты бенчмарка

Я протестировал разные порядки B-деревьев для нашей базы данных IoT с одним миллионом показаний датчика:

Датасет: 1 000 000 элементов, 10 000 случайных операций поиска

Красно-чёрное дерево:
  Высота: 20 уровней
  Такты/операции поиска: 12 000
  Промахи кэша: 18,5

B-дерево (порядок 16):
  Высота: 5 уровней
  Такты/операции поиска: 3 200
  Промахи кэша: 4,8
  Ускорение: 3,75×

B-дерево (порядок 64):
  Высота: 3 уровня
  Такты/операции поиска: 1 800
  Промахи кэша: 2,8
  Ускорение: 6,7×

B-дерево (порядок 256):
  Высота: 2 уровня
  Такты/операции поиска: 1 200
  Промахи кэша: 1,9
  Ускорение: 10×

В нашем случае идеально подходило B-дерево порядка 64 — оно оказалось в 6,7 раза быстрее красно-чёрного дерева.

Почему это сработало:

Меньше уровней: 3 против 20, а значит, 3 промаха кэша против 20.
Последовательные ключи: двоичный поиск внутри каждого узла удобен для кэша.
Амортизированные затраты: затраты на поиск внутри узла (log₆₄ ≈ 6 сравнений) очень малы по сравнению с затратами на промах кэша (100 тактов).

Выбор порядка B-дерева

Компромисс: Больше порядок → меньше уровней, но больше сравнений на узел.

Оптимальный порядок: при котором узел умещается в одну линию кэша (64 байта).

Анализ линий кэша

Порядок 4 (3 ключа):

struct btree_node {
    int num_keys;        // 4 байта
    int keys[3];         // 12 байт
    void *values[3];     // 24 байта
    void *children[4];   // 32 байта
    // Итого: 72 байта (2 линии кэша)
};

Порядок 8 (7 ключей):

struct btree_node {
    int num_keys;        // 4 байта
    int keys[7];         // 28 байт
    void *values[7];     // 56 байт
    void *children[8];   // 64 байта
    // Итого: 152 байта (3 линии кэша)
};

Рекомендация:

Хранящееся в памяти B-дерево: порядок 16-64 (нужно уравновесить высоту с размером узла).
B-дерево с хранением на диске: порядок 128-512 (минимизирует поиск по диску).

Вставка в B-дерево

Сложность: поддержание сбалансированности (все листья на одной высоте).

Стратегия: разделение заполненных узлов.

Алгоритм вставки

void btree_insert(btree_node_t **root, int key, void *value) {
    btree_node_t *node = *root;

    // Если корень заполнен, разделяем его
    if (node->num_keys == BTREE_ORDER - 1) {
        btree_node_t *new_root = create_node();
        new_root->children[0] = node;
        split_child(new_root, 0);
        *root = new_root;
    }

    insert_non_full(*root, key, value);
}

void insert_non_full(btree_node_t *node, int key, void *value) {
    int i = node->num_keys - 1;

    if (!node->children[0]) {  // Узел-лист
        // Сдвигаем ключи, чтобы освободить место
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            node->values[i + 1] = node->values[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->values[i + 1] = value;
        node->num_keys++;
    } else {  // Внутренний узел
        // Находим дочерний элемент для опускания
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;

        // Разделяем дочерний элемент, если он заполнен
        if (node->children[i]->num_keys == BTREE_ORDER - 1) {
            split_child(node, i);
            if (key > node->keys[i]) i++;
        }

        insert_non_full(node->children[i], key, value);
    }
}

Разделение узлов

Пример (порядок 4, максимум 3 ключа):

До разделения:
  Узел: [10|20|30]  (заполнен)

После разделения:
  Левый:  [10]
  Родительский: [20]
  Правый: [30]

Затраты: O(M) на разделение (копирование ключей), но амортизированное O(1) (происходит редко).

Деревья B+: оптимизация под запросы диапазонов

Проблема B-дерева: значения разбросаны по всем уровням.

Дерево B+: все значения находятся в листьях, внутренние узлы хранят только ключи.

Структура:

Внутренние узлы (только ключи):
                [40|80]
               /   |   \
Узлы-листья (ключи + значения):
  [10:v1|20:v2|30:v3] → [40:v4|50:v5|60:v6] → [80:v7|90:v8|100:v9]
   ↑                      ↑                      ↑
   └──────────────────────┴──────────────────────┘
    Связанный список для сканирования диапазонов

Преимущества:

Запросы по диапазонам: сканирование связанного списка листьев (последовательный доступ).
Более широкое разветвление: внутренние узлы меньше (нет значений).
Все данные хранятся в листьях: упрощает код.

Сценарий использования: базы данных (MySQL InnoDB, PostgreSQL, SQLite).

B-деревья, не зависящие от кэша

Проблема: оптимальный порядок B-дерева зависит от размера линии кэша (64 байта на x86, 128 байт на некоторых ARM).

Не зависящее от кэша B-дерево: адаптируется под любой размер кэша, не требуя настройки.

Принцип: рекурсивная схема (схема ван Эмде Боаса).

Пример (16 ключей):

Схема памяти:
[8]     [4|12]   [2|6|10|14] [1|3|5|7|9|11|13|15]
 ↑         ↑          ↑               ↑
Корень Уровень 1  Уровень 2        Листья

Последовательное в памяти, но логически устроено, как дерево

Преимущество: хорошо работает с разными размерами кэша.

Недостаток: сложная реализация, сложнее изменять.

Пример из реальной жизни: B-дерево SQLite

Сценарий использования: встроенная база данных (браузеры, мобильные приложения).

Архитектура:

Размер страницы: 4 КБ (соответствует размеру блока файловой системы).
Порядок: ~340 (4 КБ / 12 байт на элемент).
Дерево B+: все данные находятся в листьях.

Оптимизация: кэш страниц в памяти.

Бенчмарк (1 миллион элементов):

Поиск:
  В памяти:  1 200 тактов (3 уровней, все находятся в кэше)
  На диске:    8 мс (3 операции дискового поиска)

Сканирование диапазона (1000 элементов):
  В памяти:  180 000 тактов (последовательное сканирование листьев)
  На диске:    12 мс (последовательное чтение с диска)

Зачем использовать B-дерево в случае диска:

Минимизация операций поиска: 3 операции против 20 (BST).
Последовательное чтение: узлы-листья связаны.
Выравнивание по странице: каждый узел = один блок диска.

Встраиваемые системы: B-деревья фиксированного размера

Сложность: во встраиваемых системах нет динамического распределения.

Решение: заранее распределить узлы B-дерева в массиве.

#define MAX_NODES 1024
#define BTREE_ORDER 16

typedef struct {
    int num_keys;
    int keys[BTREE_ORDER - 1];
    void *values[BTREE_ORDER - 1];
    uint16_t children[BTREE_ORDER];  // Индексы, а не указатели
} btree_node_t;

typedef struct {
    btree_node_t nodes[MAX_NODES];
    uint16_t root;
    uint16_t free_list;
} btree_t;

Преимущества:

Без malloc: предсказуемый объём используемой памяти.
Удобство для кэша: узлы находятся в сплошном массиве.
Индексы вместо указателей: экономит память (2 байта против 8 байтов).

Недостаток: фиксированная ёмкость (MAX_NODES).

Методики оптимизации

1. Групповая загрузка

Проблема: вставка отсортированных данных по отдельности происходит медленно.

Решение: строить B-дерево снизу вверх.

btree_t* bulk_load(int *keys, void **values, int n) {
    // Сортируем входные данные
    qsort_pairs(keys, values, n);

    // Создаём листья
    int num_leaves = (n + BTREE_ORDER - 2) / (BTREE_ORDER - 1);
    btree_node_t *leaves = build_leaves(keys, values, n);

    // Строим внутренние уровни снизу вверх
    while (num_leaves > 1) {
        leaves = build_level(leaves, num_leaves);
        num_leaves = (num_leaves + BTREE_ORDER - 1) / BTREE_ORDER;
    }

    return leaves;  // Корень
}

Ускорение: в 10-100 раз быстрее, чем отдельные вставки.

2. Сжатие префиксов

Наблюдение: у ключей часто бывают общие префиксы (например, URL, пути к файлам).

Оптимизация: сохранять общий префикс один раз на узел.

struct compressed_node {
    char prefix[32];         // Общий префикс
    int prefix_len;
    char suffixes[BTREE_ORDER][32];  // Только уникальные части
};

Экономия: снижение объёма занимаемой памяти на 50-80% для ключей-строк.

3. SIMD-поиск

Идея: использовать SIMD для сравнения ключей со множеством ключей узлов параллельно.

#include <immintrin.h>

int simd_search(int *keys, int n, int target) {
    __m256i target_vec = _mm256_set1_epi32(target);

    for (int i = 0; i < n; i += 8) {
        __m256i keys_vec = _mm256_loadu_si256((__m256i*)&keys[i]);
        __m256i cmp = _mm256_cmpeq_epi32(keys_vec, target_vec);
        int mask = _mm256_movemask_epi8(cmp);
        if (mask) {
            return i + __builtin_ctz(mask) / 4;
        }
    }
    return -1;
}

Ускорение: в 2-3 раза для крупных узлов (порядок 64+).

Подведём итог

Загадка базы данных была решена. B-дерево обеспечило скорость запросов в 6,7 раз выше, чем красно-чёрное дерево, снизив время поиска с 12000 до 1800 тактов. Количество промахов кэша снизилось с 18,5 до 2,8 на операцию поиска. Теперь IoT-устройство может с лёгкостью обрабатывать запросы датчика в реальном времени. Структура данных, предназначенная «только для диска», оказалась идеальной для оптимизации кэша базы данных, хранящейся в памяти.

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

Высота дерева более важна, чем сложность узлов. B-дерево с 3 уровнями побеждает двоичное дерево с 20 уровнями даже несмотря на то, что для поиска в узле B-дерева требуется больше сравнений.
Крайне важна последовательная схема памяти. Благодаря хранению всех ключей в узле последовательно двоичный поиск внутри узла становится удобным для кэша. При единственном промахе кэша загружается весь узел.
B-деревья подходят не только для диска. В учебниках рассказывают, что B-деревья предназначены для баз данных на диске, но в случае больших датасетов они столь же ценны для структур данных в памяти.
Важен порядок. Если он слишком маленький (порядок 4-8), то высота снизится недостаточно. Если слишком большой (порядок 256+), то узлы не уместятся в кэш. Для B-деревьев в памяти идеальный порядок находится в диапазоне 16-64.
Для запросов по диапазонам лучше деревья B+. Благодаря хранению всех данных в листьях и их связыванию можно сканировать диапазоны последовательно без обхода дерева.

Показатели для нашей базы данных IoT:

Красно-чёрное дерево: 12000 тактов/поиск, 18,5 промаха кэша.
B-дерево (порядок 64): 1800 тактов/поиск, 2,8 промаха кэша.
Ускорение: 6,7×.

В следующей главе: префиксные деревья и базисные деревья для сопоставления префиксов и строковых ключей.

Структуры данных на практике. Глава 10: B-деревья и деревья, эффективно использующие кэш

Оглавление