Всегда ли бинарный поиск при индексах?

Всегда ли бинарный поиск при индексах

Краткий ответ

Нет, не всегда. Индексы используют бинарный поиск только когда индекс отсортирован (B-Tree индексы). Даже с индексом поиск может быть неэффективным, если запрос неправильно сформулирован или индекс структурирован неудачно.

Типы индексов в базах данных

1. B-Tree индекс (самый распространённый)

B-Tree (сбалансированное дерево):

              [50]
            /      \
        [25]          [75]
       /    \        /    \
    [10] [30] [60] [80] [90]

PostgreSQL / MySQL:

CREATE INDEX idx_users_age ON users(age);
// B-Tree по умолчанию
// Поддерживает: =, <, >, <=, >=, BETWEEN

Поиск в B-Tree: O(log N) — логарифмическая сложность

SELECT * FROM users WHERE age = 25;
// Бинарный поиск по B-Tree: log(1000000) ~ 20 операций

2. Hash индекс

CREATE INDEX idx_email_hash ON users USING HASH(email);
// Поддерживает только: = (точное совпадение)
// NOT поддерживает: <, >, BETWEEN

Поиск в Hash индексе: O(1) — констант

SELECT * FROM users WHERE email = 'john@example.com';
// O(1) — очень быстро, но только для точного совпадения

SELECT * FROM users WHERE email LIKE 'john%';
// ❌ Hash индекс НЕ используется для LIKE

3. GiST / GIN индексы (PostgreSQL)

CREATE INDEX idx_tags_gin ON articles USING GIN(tags);
// Для: массивов, JSONB, полнотекстового поиска

CREATE INDEX idx_text_search ON articles 
  USING GIN(to_tsvector('english', content));
// Полнотекстовый поиск — не бинарный, а инвертированный индекс

4. BRIN индекс (PostgreSQL)

CREATE INDEX idx_timestamp_brin ON logs USING BRIN(created_at);
// Для очень больших таблиц с отсортированными данными
// Не хранит каждое значение, а диапазоны
// Поиск: сначала найти блок, потом линейный поиск в блоке

Когда индекс НЕ используется

1. Функция на индексированной колонке

// ❌ Индекс НЕ используется
SELECT * FROM users WHERE UPPER(name) = 'JOHN';
SELECT * FROM orders WHERE DATE(created_at) = '2024-01-01';
SELECT * FROM products WHERE price * quantity > 1000;

// ✅ Используется индекс
SELECT * FROM users WHERE name = 'john'; // Точное совпадение
SELECT * FROM orders WHERE created_at::date = '2024-01-01';
SELECT * FROM products WHERE price > 100;

Решение — функциональный индекс:

CREATE INDEX idx_users_name_upper ON users(UPPER(name));
SELECT * FROM users WHERE UPPER(name) = 'JOHN'; // Теперь работает!

2. OR условие без индекса на все колонки

// Индекс idx_age только на age
CREATE INDEX idx_age ON users(age);

// ❌ Индекс НЕ используется на name
SELECT * FROM users WHERE age = 25 OR name = 'John';
// База проверит индекс для age, но для name нужен полный scan

// ✅ Создать составной индекс или индексы на обе колонки
CREATE INDEX idx_age_name ON users(age, name);
SELECT * FROM users WHERE age = 25 OR name = 'John'; // Теперь быстрее

3. Неправильный тип данных для сравнения

// Колонка age INTEGER, но сравнивается как строка
SELECT * FROM users WHERE age = '25'; // Может не использовать индекс
SELECT * FROM users WHERE age = 25; // Использует индекс

// Неправильное сравнение дат
SELECT * FROM orders WHERE created_at = '2024-01-01';
// created_at — TIMESTAMP, сравниваем со строкой
// ❌ Может не использовать индекс

SELECT * FROM orders WHERE created_at >= '2024-01-01'::timestamp AND created_at < '2024-01-02'::timestamp;
// ✅ Правильно типизировано

4. LIKE с % в начале

CREATE INDEX idx_email ON users(email); -- B-Tree индекс

// ✅ Индекс используется (% в конце)
SELECT * FROM users WHERE email LIKE 'john%';
// B-Tree может найти первый 'john', потом сканить дальше

// ❌ Индекс НЕ используется (% в начале)
SELECT * FROM users WHERE email LIKE '%example.com';
// Невозможно использовать B-Tree, нужен полный scan

// Решение — GIN индекс с trigram
CREATE EXTENSION pg_trgm;
CREATE INDEX idx_email_trgm ON users USING GIN(email gin_trgm_ops);
SELECT * FROM users WHERE email LIKE '%example.com'; -- Теперь быстро

Составные индексы (Composite Indexes)

// Индекс на несколько колонок
CREATE INDEX idx_user_profile ON users(age, city, name);

// Порядок важен! Первая колонка — как главная ось B-Tree

// ✅ Использует индекс (первая колонка в условии)
SELECT * FROM users WHERE age = 25;
SELECT * FROM users WHERE age = 25 AND city = 'NYC';
SELECT * FROM users WHERE age = 25 AND city = 'NYC' AND name = 'John';

// ❌ Не использует индекс (пропустили age, первую колонку)
SELECT * FROM users WHERE city = 'NYC' AND name = 'John';

// ✅ Использует, но эффективнее
SELECT * FROM users WHERE age = 25 AND name = 'John';
// age отфильтрует быстро, но потом нужен дополнительный поиск по name

Параметры индекса в Node.js ORM

TypeORM:

@Entity()
export class User {
  @PrimaryGeneratedColumn()
  id: number;

  @Column()
  @Index() // B-Tree по умолчанию
  email: string;

  @Column()
  @Index({ unique: true })
  username: string;

  @Column()
  @Index('idx_age_city', { fulltext: false })
  age: number;

  @Column()
  city: string;
}

// Также можно определить в декораторе Entity
@Entity({
  indices: [
    { columns: ['email', 'city'] }, // Составной индекс
    { columns: ['age'], where: 'age > 18' } // Partial index
  ]
})

Sequelize:

const User = sequelize.define('User', {
  email: {
    type: DataTypes.STRING,
    index: true // B-Tree
  },
  age: {
    type: DataTypes.INTEGER,
    index: {
      type: 'HASH' // Hash индекс
    }
  }
}, {
  indexes: [
    { fields: ['email', 'city'] }, // Составной
    { fields: ['age'], where: { active: true } } // Partial
  ]
});

Частые ошибки

// ❌ Ошибка 1: Индекс не используется из-за функции
CREATE INDEX idx_name ON users(name);
SELECT * FROM users WHERE LOWER(name) = 'john';
// Индекс не используется!

// ✅ Решение
CREATE INDEX idx_name_lower ON users(LOWER(name));

// ❌ Ошибка 2: Слишком много индексов
CREATE INDEX ON users(id);
CREATE INDEX ON users(email);
CREATE INDEX ON users(name);
CREATE INDEX ON users(age);
CREATE INDEX ON users(city);
// Замедляет INSERT/UPDATE/DELETE!

// ✅ Решение
CREATE INDEX ON users(email); // Часто ищется
CREATE INDEX ON users(age, city); // Часто вместе

// ❌ Ошибка 3: Индекс на редко используемые колонки
CREATE INDEX ON users(middle_name);
// Редко используется — напрасно занимает место

Проверка использования индекса

// PostgreSQL
EXPLAIN ANALYZE
SELECT * FROM users WHERE age = 25;

// Результат показывает: "Index Scan" или "Seq Scan" (полный скан)

// MySQL
EXPLAIN
SELECT * FROM users WHERE age = 25;
// Колонка 'key' показывает какой индекс использован

Вывод

• Индексы не всегда автоматически используются — условие запроса должно быть совместимо с индексом
• B-Tree индексы используют бинарный поиск — O(log N)
• Hash индексы — O(1) для точного поиска
• Функции на индексированных колонках отключают индекс
• LIKE с % в начале не использует B-Tree
• Составные индексы требуют порядка колонок
• Всегда проверяй EXPLAIN/EXPLAIN ANALYZE для подтверждения