Что такое B-trees и B+ trees и почему их используют базы данных?

Question

IT Interview Practice · Accepted Answer

**B-tree** — это самобалансирующееся дерево поиска, в котором каждый узел содержит **много ключей** и имеет **много потомков** (высокий *fanout*). Это делает дерево **неглубоким**, минимизируя количество **дисковых операций чтения** — ровно то, что нужно базам данных и файловым системам. ## Почему высокий fanout превосходит двоичное дерево ```text Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks) B-tree, 100 keys/node -> height ~3 (3 disk seeks) Each node = one disk block/page read. ``` ## Структура (B-tree порядок 4) ```text [ 17 | 35 ] / | \ [4|9|12] [20|28] [40|50|60] each node packs many keys -> few levels ``` ## Усовершенствование B+ tree В **B+ tree** *все значения находятся в листьях* и листья **связаны**, поэтому сканирование диапазона проходит по связному списку листьев — идеально для запросов типа `WHERE age BETWEEN 20 AND 40`. ```text internal nodes: keys only (routing) leaves: [..]<->[..]<->[..] <- linked for fast range scans ``` ## Сложность | Операция | Время | Дисковые операции ввода-вывода | |---|---|---| | search | O(log n) | O(height) | | insert / delete | O(log n) | O(height) | | range scan | O(log n + k) | sequential leaves | ## Почему это важно Доступ к диску и SSD на порядки медленнее, чем к памяти, поэтому важный показатель — **количество дисковых операций, а не сравнений**. Высокий fanout резко снижает количество дисковых операций, держа дерево в глубине всего нескольких уровней. Поэтому практически каждый индекс реляционной базы данных (и многие файловые системы) построены на B+ trees вместо двоичных деревьев поиска.

Операция	Время	Дисковые операции ввода-вывода
search	O(log n)	O(height)
insert / delete	O(log n)	O(height)
range scan	O(log n + k)	sequential leaves

Почему высокий fanout превосходит двоичное дерево

Структура (B-tree порядок 4)

Усовершенствование B+ tree

Сложность

Почему это важно

Похожие вопросы