Деревья 2-3-4 и B-деревья

живой пример

public class TreeHeightDemo {
    static int levels(long keys, int keysPerNode) {
        long capacity = 1;
        int levels = 0;
        while (capacity < keys) {
            capacity *= keysPerNode + 1;
            levels++;
        }
        return levels;
    }

    public static void main(String[] args) {
        long keys = 1_000_000;
        System.out.println("двоичное дерево, 1 ключ в узле:  " + levels(keys, 1));
        System.out.println("дерево 2-3-4, 3 ключа в узле:    " + levels(keys, 3));
        System.out.println("B-дерево, 255 ключей в узле:     " + levels(keys, 255));
    }
}

живой пример

package main

import "fmt"

func levels(keys, keysPerNode int64) int {
	capacity, count := int64(1), 0
	for capacity < keys {
		capacity *= keysPerNode + 1
		count++
	}
	return count
}

func main() {
	keys := int64(1_000_000)
	fmt.Println("двоичное дерево, 1 ключ в узле: ", levels(keys, 1))
	fmt.Println("дерево 2-3-4, 3 ключа в узле:   ", levels(keys, 3))
	fmt.Println("B-дерево, 255 ключей в узле:    ", levels(keys, 255))
}

живой пример

function levels(keys, keysPerNode) {
  let capacity = 1;
  let count = 0;
  while (capacity < keys) {
    capacity *= keysPerNode + 1;
    count++;
  }
  return count;
}

const keys = 1_000_000;
console.log("двоичное дерево, 1 ключ в узле: ", levels(keys, 1));
console.log("дерево 2-3-4, 3 ключа в узле:   ", levels(keys, 3));
console.log("B-дерево, 255 ключей в узле:    ", levels(keys, 255));

живой пример

def levels(keys: int, keys_per_node: int) -> int:
    capacity, count = 1, 0
    while capacity < keys:
        capacity *= keys_per_node + 1
        count += 1
    return count


keys = 1_000_000
print("двоичное дерево, 1 ключ в узле: ", levels(keys, 1))
print("дерево 2-3-4, 3 ключа в узле:   ", levels(keys, 3))
print("B-дерево, 255 ключей в узле:    ", levels(keys, 255))

Берут TreeMap (и TreeSet поверх него). Внутри у него красно-чёрное дерево, а оно, как мы только что видели, — то же 2-3-4 в двоичной записи: 3-узел разворачивается в чёрный узел с одним красным потомком, 4-узел — в чёрный с двумя красными, а разбиение превращается в перекраску. Обещанная сложность та же: get, put, remove — гарантированные O(log n) при любом порядке данных.

Самого дерева 2-3-4 в java.util нет, как и B-дерева, и это не упущение. Весь выигрыш B-дерева — в экономии обращений к внешнему хранилищу: широкий узел окупается тогда, когда за одно чтение вы поднимаете с диска целый блок. java.util работает с тем, что уже лежит в памяти, и никакого диска под ним нет. Поэтому B-деревья в Java-мире живут не в коллекциях, а внутри баз данных, встраиваемых хранилищ и файловых систем — там, где чтение стоит дорого.

Вторая разница — в диапазонных запросах.

живой пример

import java.time.LocalDate;
import java.util.TreeMap;

public class RangeDemo {
    public static void main(String[] args) {
        TreeMap<LocalDate, String> orders = new TreeMap<>();
        orders.put(LocalDate.parse("2026-03-01"), "A-1");
        orders.put(LocalDate.parse("2026-03-07"), "A-2");
        orders.put(LocalDate.parse("2026-03-19"), "A-3");
        orders.put(LocalDate.parse("2026-04-02"), "A-4");
        System.out.println(orders.subMap(
                LocalDate.parse("2026-03-05"), true,
                LocalDate.parse("2026-03-25"), true));
    }
}

Такой диапазон TreeMap собирает обходом дерева — прыжками вверх-вниз по ссылкам. В B+-дереве листья дополнительно связаны в цепочку, поэтому диапазон — это один спуск и линейное чтение подряд идущих блоков. Ровно поэтому выборка «с даты по дату» по индексированной колонке в базе данных стоит так дёшево.

Грабля. Соблазн «закешировать таблицу в TreeMap, чтобы не ходить в базу» работает ровно до тех пор, пока данные помещаются в память с запасом. Каждая запись — отдельный объект-узел: на миллионах записей это миллионы объектов, давление на сборщик мусора и долгое восстановление после перезапуска, потому что дерево строится заново. Порог, за которым пора возвращаться к индексу в базе, задаётся не O-нотацией — она у обеих структур логарифмическая, — а объёмом данных и тем, сколько у вас памяти.

Ни дерева 2-3-4, ни B-дерева, ни красно-чёрного в стандартной библиотеке Go нет: упорядоченную структуру в памяти собирают из отсортированного среза или берут пакетом. И это не упущение. Весь выигрыш B-дерева — в экономии обращений к внешнему хранилищу: широкий узел окупается тогда, когда за одно чтение вы поднимаете с диска целый блок. Стандартная библиотека работает с тем, что уже лежит в памяти, и никакого диска под ней нет.

Зато в мире Go B-дерево живёт на удивление близко к прикладному коду. Пакет github.com/google/btree — это B-дерево в памяти: узел по умолчанию держит до 63 ключей, потому что широкий узел окупается не только на диске, но и в кеше процессора, и именно на нём etcd и Kubernetes держат свои индексы. На диске то же дерево, уже B+, лежит в bbolt, встраиваемом хранилище, на котором etcd хранит данные: файл, отображённый в память, страницы по 4 КБ, ключи в листьях подряд. Обещанная сложность у обоих та же: поиск, вставка, удаление — гарантированные O(log n) при любом порядке данных.

Вторая разница — в диапазонных запросах. У отсортированного среза диапазон это два двоичных поиска и срез между ними:

живой пример

package main

import (
	"fmt"
	"slices"
	"strings"
)

func main() {
	days := []string{"2026-03-01", "2026-03-07", "2026-03-19", "2026-04-02"}
	codes := map[string]string{"2026-03-01": "A-1", "2026-03-07": "A-2", "2026-03-19": "A-3", "2026-04-02": "A-4"}
	lo, _ := slices.BinarySearchFunc(days, "2026-03-05", strings.Compare)
	hi, _ := slices.BinarySearchFunc(days, "2026-03-26", strings.Compare)
	for _, day := range days[lo:hi] {
		fmt.Println(day, codes[day])
	}
}

Даты в формате ISO сравниваются как строки правильно, поэтому strings.Compare здесь достаточно. Дерево в памяти тот же диапазон собирает обходом — прыжками вверх-вниз по указателям, у google/btree для этого есть AscendRange. В B+-дереве листья дополнительно связаны в цепочку, поэтому диапазон — это один спуск и линейное чтение подряд идущих блоков. Ровно поэтому выборка «с даты по дату» по индексированной колонке в базе данных стоит так дёшево.

Грабля. Соблазн «закешировать таблицу в map или срез, чтобы не ходить в базу» работает ровно до тех пор, пока данные помещаются в память с запасом. Миллионы записей в map со строковыми ключами это миллионы объектов и заметная пауза сборщика мусора на каждом цикле, а после перезапуска кеш строится заново. Порог, за которым пора возвращаться к индексу в базе, задаётся не O-нотацией — она у обеих структур логарифмическая, — а объёмом данных и тем, сколько у вас памяти.

Ни дерева 2-3-4, ни B-дерева, ни красно-чёрного в стандартной библиотеке JavaScript нет: упорядоченную структуру в памяти собирают из отсортированного массива или берут пакетом вроде sorted-btree. И это не упущение. Весь выигрыш B-дерева — в экономии обращений к внешнему хранилищу: широкий узел окупается тогда, когда за одно чтение вы поднимаете с диска целый блок. Стандартная библиотека работает с тем, что уже лежит в памяти, и никакого диска под ней нет.

Зато B-деревья окружают код на Node со всех сторон. Встраиваемая SQLite, которую приложения на Node подключают через better-sqlite3, а с Node 22 и через встроенный модуль node:sqlite, хранит таблицы и индексы B-деревьями со страницами по 4 КБ; IndexedDB в браузере лежит поверх LevelDB, у которой на диске уже не B-дерево, а LSM-дерево, тот же ответ на ту же задачу с другим компромиссом между чтением и записью. Обещанная сложность везде та же: поиск, вставка, удаление — гарантированные O(log n) при любом порядке данных.

Вторая разница — в диапазонных запросах. У отсортированного массива диапазон это два двоичных поиска и slice между ними:

живой пример

function lowerBound(a, key) {
  let lo = 0;
  let hi = a.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (a[mid] < key) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

const orders = [["2026-03-01", "A-1"], ["2026-03-07", "A-2"], ["2026-03-19", "A-3"], ["2026-04-02", "A-4"]];
const days = orders.map(([day]) => day);
const from = lowerBound(days, "2026-03-05");
const to = lowerBound(days, "2026-03-26");
console.log(orders.slice(from, to));

Даты в формате ISO сравниваются как строки правильно, поэтому обычного < здесь достаточно. Дерево в памяти тот же диапазон собирает обходом — прыжками вверх-вниз по ссылкам. В B+-дереве листья дополнительно связаны в цепочку, поэтому диапазон — это один спуск и линейное чтение подряд идущих блоков. Ровно поэтому выборка «с даты по дату» по индексированной колонке в базе данных стоит так дёшево.

Грабля. Соблазн «закешировать таблицу в Map, чтобы не ходить в базу» работает ровно до тех пор, пока данные помещаются в память с запасом. У процесса Node куча по умолчанию ограничена парой гигабайт, миллионы записей в Map это миллионы объектов и долгие паузы сборщика мусора, а после перезапуска кеш строится заново. Порог, за которым пора возвращаться к индексу в базе, задаётся не O-нотацией — она у обеих структур логарифмическая, — а объёмом данных и тем, сколько у вас памяти.

Ни дерева 2-3-4, ни красно-чёрного в стандартной библиотеке Python нет: упорядоченную структуру в памяти собирают из отсортированного списка с bisect или берут sortedcontainers. И это не упущение. Весь выигрыш B-дерева — в экономии обращений к внешнему хранилищу: широкий узел окупается тогда, когда за одно чтение вы поднимаете с диска целый блок, а bisect работает с тем, что уже лежит в памяти.

А вот само B-дерево в стандартной библиотеке Python есть, только не в виде коллекции: модуль sqlite3 возит с собой встраиваемую базу, и каждая её таблица и каждый индекс — это B-дерево на страницах по 4 КБ. То есть индекс с диапазонным запросом доступен без единой зависимости:

живой пример

import sqlite3

db = sqlite3.connect(":memory:")
db.execute("create table orders(day text primary key, code text)")
db.executemany("insert into orders values (?, ?)", [
    ("2026-03-01", "A-1"), ("2026-03-07", "A-2"), ("2026-03-19", "A-3"), ("2026-04-02", "A-4"),
])
print(db.execute("select day, code from orders where day between '2026-03-05' and '2026-03-25'").fetchall())
for row in db.execute("explain query plan select * from orders where day between '2026-03-05' and '2026-03-25'"):
    print(row[-1])

Первичный ключ создал индекс, и план запроса показывает SEARCH ... USING INDEX: база спустилась по B-дереву к первой дате и прочитала листья подряд до последней. Обещанная сложность та же, что у дерева в памяти: поиск, вставка, удаление — гарантированные O(log n) при любом порядке данных.

Вторая разница — в диапазонных запросах в памяти. У отсортированного списка диапазон это два bisect и срез между ними, days[bisect_left(days, "2026-03-05"):bisect_left(days, "2026-03-26")], даты в формате ISO сравниваются как строки правильно. Дерево в памяти тот же диапазон собирает обходом — прыжками вверх-вниз по ссылкам. В B+-дереве листья дополнительно связаны в цепочку, поэтому диапазон — это один спуск и линейное чтение подряд идущих блоков. Ровно поэтому выборка «с даты по дату» по индексированной колонке в базе данных стоит так дёшево.

Грабля. Соблазн «закешировать таблицу в dict, чтобы не ходить в базу» работает ровно до тех пор, пока данные помещаются в память с запасом. Каждая запись в Python — несколько объектов: ключ, значение, их поля; на миллионах записей это гигабайты, паузы сборщика мусора и долгое восстановление после перезапуска, потому что кеш строится заново. Порог, за которым пора возвращаться к индексу в базе, задаётся не O-нотацией — она у обеих структур логарифмическая, — а объёмом данных и тем, сколько у вас памяти.