В индексах чаще всего используют следующие структуры данных: - **B-деревья (B-Tree)** ``` # Пример индексации в SQL (не Python, но для понимания) CREATE INDEX idx_name ON users(name); ``` - Балансированные деревья с высокой производительностью для диапазонных запросов и операций вставки/удаления. - Используются в реляционных БД (PostgreSQL, MySQL). - **Хеш-таблицы** ``` # Пример словаря (аналог хеш-таблицы) index = {"id1": "data1", "id2": "data2"} ``` - Оптимальны для точечных запросов (O(1) в среднем). - Не поддерживают диапазонные запросы. - **LSM-деревья (Log-Structured Merge-Tree)** - Используются в NoSQL (RocksDB, Cassandra) для оптимизации записи. - **Битовые индексы (Bitmap)** - Эффективны для столбцов с малым количеством уникальных значений. **Нюансы:** - B-деревья доминируют в OLTP-системах из-за баланса чтения/записи. - LSM-деревья предпочитают в write-intensive сценариях.