Ограничения B+ Tree

1. Проблема ведущего Wildcard (LIKE '%smith%')

Представь B+ дерево как алфавитный указатель. Если ты ищешь всех на букву «Ива» (LIKE 'Ива%'), ты быстро находишь раздел «И», потом «Ив» и читаешь Ивановых. Дерево отсортировано, индекс работает великолепно.

А теперь представь, что тебе нужно найти LIKE '%smith%' (где-то в строке есть smith). Это может быть Aerosmith, Blacksmith или Goldsmith. Индекс отсортирован только по началу строки! База не знает, куда спускаться, поэтому она отключает индекс и делает полное сканирование таблицы (Full Scan), убивая производительность.

2. Фрагментация

После множества разделений (Node Splits) и удалений, узлы дерева редко заполнены на 100%. Обычно они полупустые. Это значит, что индекс на диске занимает больше места, чем сами полезные данные.

3. Конкуренция за корень

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

• MySQL (InnoDB): Использует B+ деревья для всех индексов. Более того, сами строки таблицы физически хранятся прямо в листьях главного B+ дерева! Это называется Кластерный индекс (Clustered Index) — о нем мы поговорим в следующих главах.
• PostgreSQL: Тоже живет на B+ деревьях, но с крутой фишкой — дедупликацией. Если у тебя есть тысяча строк со статусом 'active', Postgres не будет хранить слово 'active' тысячу раз в индексе. Он сохранит его один раз и привяжет к нему массив ссылок, экономя огромное количество памяти.