Юлдашев_Диёрбек_Структуры_данных_для_индексирования_хеш_таблицы

1.

ОБРАЗОВАТЕЛЬНЫЙ КУРС
Структуры данных
для индексирования
Хеш-таблицы и деревья — фундаментальные структуры, лежащие
в основе баз данных и поисковых систем
Базы данных
Поисковые системы
Кеширование

2.

ПРОБЛЕМА И РЕШЕНИЕ
Зачем нужно индексирование?
Как индексы превращают медленный поиск в мгновенный
Полное сканирование
Поиск с индексом
Без индекса база данных проверяет каждую строку таблицы
Временная сложность
O(n)
Индекс создаёт структуру данных для мгновенного доступа
Временная сложность
O(log n) / O(1)
Пример: Поиск в таблице с 1 млн записей требует до 1 000 000
Результат: Тот же поиск требует всего ~20 операций (дерево) или
операций
1 операцию (хеш)
Ключевая идея: Индекс — это дополнительная структура данных, которая «показывает путь» к нужным записям, избегая полного
сканирования

3.

ХЕШ-ТАБЛИЦЫ
Принцип работы хеш-таблиц
Мгновенный доступ через хеш-функцию
Как работает хеш-таблица
Скорость операций
Вставка (insert)
O(1)
Добавление новой пары
"user_123"
hash()
42
Ключ
Хеш-функция
Индекс
Поиск (lookup)
O(1)
Получение значения по ключу
Удаление (delete)
0
1
42
3
4
...
O(1)
Удаление пары ключ-значение
n
user_123
Массив (бакеты)
Ключевая особенность
Все операции выполняются за константное время в среднем
случае, независимо от размера таблицы
Коэффициент загрузки
Оптимальный λ
При λ > 0.75
λ = n/m
0.5 - 0.75
Рехеширование

4.

ПРОБЛЕМА И РЕШЕНИЕ
Коллизии и методы разрешения
Что происходит, когда два ключа дают один индекс?
Метод цепочек
1
Каждый бакет содержит указатель на список элементов с одинаковым
2
Открытая адресация
При коллизии ищем следующий свободный слот в массиве
хешем
Индекс
2
Индекс
5
Индекс
2
"Anna" → 25
"Alex" → 30
Индекс 0
пусто
Индекс 1
"Bob"
Индекс 2
"Anna"
Индекс 3
"Alex" (коллизия)
Индекс 4
пусто
"Bob" → 35
"Alice" → 28
Плюсы: Простота, таблица никогда не переполняется
Линейное пробирование: +1, +2, +3...
Минусы: Дополнительная память на указатели
Проблема: Первичное кластерирование
Важно: Хорошая хеш-функция минимизирует коллизии. В среднем случае длина цепочки = коэффициент загрузки (λ)

5.

ДЕРЕВЬЯ
Деревья поиска
От бинарных деревьев к B-деревьям
Бинарное дерево поиска (BST)
Проблема вырождения
При вставке отсортированных данных BST превращается в список:
10
20
30
40
Результат: Поиск становится O(n) вместо O(log n)
Свойство BST: Все значения в левом поддереве меньше корня, в правом —
больше
Решение: B-деревья
Узлы содержат несколько ключей, что снижает высоту дерева и

6.

B+ ДЕРЕВЬЯ
B+ деревья в базах данных
Почему все major СУБД используют именно их
Структура B+ дерева
Ключевые особенности
Все данные в листьях
Внутренние узлы только для навигации
Связанные листья
Эффективный диапазонный поиск O(log n + k)
Множественные ключи в узле
Снижает высоту дерева и дисковые операции
Самобалансировка
Все листья на одном уровне
Производительность
Поиск:
O(log n)
Вставка:
O(log n)
Удаление:
O(log n)
Range query:
O(log n + k)
Пример: Для 1 млн записей высота B+ дерева с fanout=100 всего 3 уровня (против 20 у обычного BST), что означает только 3 дисковые операции

7.

СРАВНЕНИЕ
Хеш-таблицы vs Деревья
Когда использовать каждую структуру данных
Характеристика
Хеш-таблицы
B+ Деревья
Поиск по ключу
O(1)
O(log n)
Диапазонный поиск
O(n)
O(log n + k)
Сортировка
❌ Нет
✅ Да
Ближайший элемент
❌ Нет
✅ Да
Потребление памяти
Выше
Ниже
O(n) worst case
O(log n) гарантия
Средняя
Высокая
Предсказуемость
Кеш-эффективность
Хеш-таблицы лучше
Точный поиск, кеширование, уникальные ID
Деревья лучше
Диапазоны, сортировка, упорядоченность
В базах данных
B+ деревья для индексов, хеши для кеша

8.

ПРАКТИЧЕСКИЕ РЕКОМЕНДАЦИИ
Когда что использовать?
Реальные сценарии из индустрии
Хеш-таблицы
B+ Деревья
Точный поиск по ключу
Диапазонные запросы
Поиск пользователя по ID, проверка существования элемента
WHERE age BETWEEN 20 AND 30, даты, цены
Кеширование
Redis, Memcached — хранение часто запрашиваемых данных
Сортировка и ORDER BY
Индексы автоматически поддерживают порядок
Подсчет частоты
Префиксный поиск
Word count, аналитика в реальном времени
WHERE name LIKE 'John%', поиск по началу строки
Примеры: HashMap (Java), dict (Python), unordered_map (C++)
СУБД: MySQL InnoDB, PostgreSQL, MongoDB, SQLite — все используют B+ деревья
Ключевой вывод
В реальных системах часто используются обе структуры: B+ деревья для первичных/вторичных индексов в СУБД, хеш-таблицы для кешей и быстрого точного поиска.
Понимание их сильных сторон помогает принимать правильные архитектурные решения.