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

B-tree (сбалансированное дерево) — это структура данных, используемая для индексов в базах данных. Она представляет собой дерево с несколькими ключами в каждом узле и несколькими потомками, что позволяет хранить данные отсортированными и быстро находить нужные записи.

Как работает B-tree индекс:

Каждый узел содержит несколько ключей и указателей на дочерние узлы.
Все ключи в левом поддереве меньше ключа в узле, а в правом — больше.
При поиске по индексу алгоритм спускается по дереву, сравнивая искомое значение с ключами в узлах, выбирая нужный путь.
Дерево сбалансировано, поэтому высота дерева минимальна, что обеспечивает логарифмическое время поиска.

Пример упрощённой структуры B-tree:

// Узел B-tree
type BTreeNode struct {
    keys     []int
    children []*BTreeNode
    leaf     bool
}

// Поиск ключа в B-tree
func (n *BTreeNode) Search(key int) bool {
    i := 0
    for i < len(n.keys) && key > n.keys[i] {
        i++
    }
    if i < len(n.keys) && key == n.keys[i] {
        return true
    }
    if n.leaf {
        return false
    }
    return n.children[i].Search(key)
}

Таким образом, B-tree индекс позволяет быстро находить записи в базе, минимизируя количество операций чтения с диска.

Как внутри устроена база данных? Как работает B-tree индекс?