Как работает некластеризованный индекс?

Как работает некластеризованный индекс

Основная идея

Некластеризованный индекс (Non-Clustered Index, NCI) — это вспомогательная структура для быстрого поиска данных в таблице. В отличие от кластеризованного индекса, некластеризованный индекс НЕ определяет порядок хранения данных в таблице.

Кластеризованный vs Некластеризованный индекс

Кластеризованный индекс (Clustered Index):
- В таблице может быть ТОЛЬКО ОДИН
- Определяет физический порядок данных в таблице
- Обычно по первичному ключу (PRIMARY KEY)
- Листья индекса содержат саму строку данных

Некластеризованный индекс (Non-Clustered Index):
- Может быть ДО 999 штук на таблицу
- НЕ определяет порядок хранения
- Это отдельная структура (В-дерево)
- Листья содержат ключевые колонки + указатель на данные

Структура некластеризованного индекса

Когда индекс создан по колонке name:

Таблица Users (физический порядок в памяти):
ID | Name      | Email             | Age
---+-----------+-------------------+-----
1  | Alice     | alice@example.com | 30
2  | Bob       | bob@example.com   | 25
3  | Charlie   | charlie@ex.com    | 35
4  | Diana     | diana@ex.com      | 28
5  | Eve       | eve@example.com   | 32

Некластеризованный индекс по Name (отдельная структура):
Name (отсортирован)  |  Указатель на строку (RID)
--------------------+---------------------------
Alice               |  Row ID: 1
Bob                 |  Row ID: 2
Charlie             |  Row ID: 3
Diana               |  Row ID: 4
Eve                 |  Row ID: 5

Как работает поиск с некластеризованным индексом

Запрос: найти пользователя по имени "Bob"

SELECT * FROM Users WHERE Name = 'Bob';

Без индекса (Table Scan):

1. Сканируешь всю таблицу слева направо
2. Проверяешь каждую строку: Name == 'Bob'?
3. Сложность: O(n) — медленно!

С некластеризованным индексом (Seek + Lookup):

Шаг 1: Index Seek
Два-дерево индекса:
          [M]
         /   \
      [B-F]  [P-Z]
      /  |     
    [A][B][C][D][E] ...
          ↓
    Найден "Bob" -> RID = 2

Шаг 2: Key Lookup (или Nested Loop Join)
    Получи RID = 2
    Обратись к таблице по ID = 2
    Получи полную строку: (2, Bob, bob@example.com, 25)

Сложность: O(log n) для поиска в индексе + O(1) для доступа = O(log n)

Включаемые колонки (Included Columns)

Если часто нужны разные колонки, можно добавить их в индекс, чтобы избежать Key Lookup:

-- Без INCLUDE: поиск + обращение в таблицу
CREATE INDEX idx_name ON Users(Name);

-- С INCLUDE: всё нужное есть в индексе
CREATE INDEX idx_name_with_email 
ON Users(Name) 
INCLUDE (Email, Age);

-- Теперь запрос SELECT Email FROM Users WHERE Name = 'Bob'
-- находит всё в индексе, не обращаясь к таблице (Covering Index)

Covering Index (Покрывающий индекс)

public class CoveringIndexExample {
    
    // Таблица: (ID, Name, Email, Age, Salary, Department)
    
    // ❌ Обычный индекс: поиск + Key Lookup
    // CREATE INDEX idx1 ON Users(Department);
    // SELECT Name, Email FROM Users WHERE Department = 'Sales'
    // -> Индекс содержит только Department и RID
    // -> Нужно обратиться в таблицу за Name и Email
    
    // ✅ Covering индекс: всё в индексе
    // CREATE INDEX idx2 ON Users(Department) INCLUDE (Name, Email);
    // SELECT Name, Email FROM Users WHERE Department = 'Sales'
    // -> Индекс содержит Department, Name, Email и RID
    // -> НЕ нужно обращаться в таблицу! (Index Only Scan)
}

Проблема: Фрагментация индекса

При частых вставках/обновлениях индекс становится неоптимальным:

Оптимальный индекс (плотный):
[A][B][C][D][E][F][G][H]
    ↑ узлы идут подряд

Фрагментированный индекс:
[A]   [C]      [E]   [G]
   ↑ есть пробелы
   → нужно больше операций ввода-вывода

Решение: перестроить индекс

-- Проверить уровень фрагментации
SELECT * FROM sys.dm_db_index_physical_stats(
    DB_ID(), 
    OBJECT_ID('Users'), 
    NULL, 
    NULL, 
    'LIMITED'
);

-- Перестроить (если фрагментация > 30%)
ALTER INDEX idx_name ON Users REBUILD;

-- Реорганизовать (если фрагментация 10-30%)
ALTER INDEX idx_name ON Users REORGANIZE;

Типы операций сканирования

1. Index Seek (лучший случай)
   → Идёшь прямо к нужным строкам в индексе
   → Сложность: O(log n)
   → Когда: WHERE Name = 'Bob' (точное совпадение)

2. Index Scan (плохой случай)
   → Сканируешь весь индекс слева направо
   → Сложность: O(n)
   → Когда: нет подходящего индекса или условие слишком широкое

3. Key Lookup (после Index Seek)
   → Ищешь в индексе -> находишь RID -> идёшь в таблицу
   → Сложность: O(1) на строку
   → Когда: нужны колонки, которых нет в индексе

4. Index Only Scan (лучше всех)
   → Всё нужное есть в индексе (Covering Index)
   → Не нужно обращаться в таблицу
   → Сложность: O(log n)
   → Когда: SELECT Name, Email FROM Users WHERE Department = 'Sales'
            (все колонки в индексе)

На практике: Java и ORM

В Hibernate/JPA с аннотациями:

@Entity
@Table(name = "users")
public class User {
    
    @Id
    private Long id;
    
    @Column(name = "name")
    @Index(name = "idx_name") // Некластеризованный индекс
    private String name;
    
    @Column(name = "email")
    private String email;
    
    @Column(name = "age")
    private Integer age;
}

// Миграция (Liquibase/Flyway):
// <createIndex indexName="idx_name_email" tableName="users" unique="false">
//     <column name="name"/>
//     <column name="email"/>
// </createIndex>

Когда использовать индекс

✅ ХОРОШО:
- SELECT * FROM Users WHERE id = 1
- SELECT * FROM Orders WHERE customer_id = 123
- SELECT * FROM Posts WHERE created_at > '2024-01-01'
- SELECT * FROM Users ORDER BY name  (индекс помогает сортировке)

❌ ПЛОХО:
- SELECT * FROM Users WHERE AGE * 2 = 60 (функция на индексируемой колонке)
- SELECT * FROM Users WHERE Name LIKE '%bob%' (начинается с %)
- SELECT * FROM Users WHERE YEAR(created_at) = 2024 (функция)
- SELECT * FROM SmallTable (мала таблица, индекс медленнее scan)

Стоимость индекса

Преимущества SELECT:
+ Ускорение поиска (O(log n) вместо O(n))
+ Ускорение сортировки (ORDER BY)
+ Ускорение GROUP BY

Недостатки при INSERT/UPDATE/DELETE:
- Нужно обновлять индекс (медленнее запись)
- Занимает дополнительное место на диске
- Нужно поддерживать консистентность
- Может замедлить операции, если индексов слишком много

Итого

Некластеризованный индекс — это отдельная отсортированная структура (В-дерево), которая содержит:

1. Значения индексируемых колонок
2. Row ID (указатель на данные в таблице)

Большинство СУБД использует 1-2 некластеризованных индекса на таблицу для максимальной производительности поиска.