Какие индексы ты знаешь? Как работает B-tree индекс?

Существуют разные типы индексов в базах данных, основные из них:

• B-tree (сбалансированное дерево): самый распространённый тип индекса для быстрого поиска, вставки и удаления. Данные организованы в виде дерева, где каждый узел содержит ключи и ссылки на дочерние узлы. Поиск происходит за логарифмическое время.

• Hash-индексы: используют хеш-функции для быстрого доступа по точному значению ключа, но не подходят для диапазонных запросов.

• Bitmap-индексы: эффективны для столбцов с небольшим числом уникальных значений.

• Full-text индексы: для быстрого поиска по тексту.

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

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

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