Что такое произвольный доступ в БД?

Произвольный доступ в базе данных

Произвольный доступ (Random Access) в контексте баз данных — это способность обращаться к любому блоку или записи данных без необходимости просматривать все предыдущие блоки. Это кардинально отличается от последовательного доступа (Sequential Access), где нужно читать данные по порядку.

Основные различия

Последовательный доступ (Sequential):

Для доступа к записи #1000:
Читаем запись 1 -> 2 -> 3 -> ... -> 999 -> 1000
Время = O(n) — пропорционально позиции

Произвольный доступ (Random):

Для доступа к записи #1000:
Непосредственный прыжок к записи 1000
Время = O(1) — константное время

Как работает произвольный доступ в SQL БД

import sqlite3

conn = sqlite3.connect('database.db')
cursor = conn.cursor()

# Произвольный доступ по индексу PRIMARY KEY
# Время выполнения: O(log n) в B-Tree индексе
cursor.execute('SELECT * FROM users WHERE id = ?', (12345,))
user = cursor.fetchone()  # Мгновенно находит нужную запись

# Произвольный доступ по индексированному столбцу
cursor.execute('SELECT * FROM users WHERE email = ?', ('user@example.com',))
user = cursor.fetchone()  # Использует индекс для быстрого поиска

# Последовательный доступ (МЕДЛЕННЫЙ - полная таблица сканируется)
cursor.execute('SELECT * FROM users WHERE age > 18')
# Если нет индекса на age, БД проверит ВСЕ строки
users = cursor.fetchall()  # O(n) — медленнее для больших таблиц

Индексы как основа произвольного доступа

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

# Создание индекса для произвольного доступа
cursor.execute('CREATE INDEX idx_users_email ON users(email)')

# Теперь поиск по email — произвольный доступ (O(log n))
cursor.execute('SELECT * FROM users WHERE email = ?', ('john@example.com',))
# Выполнение: логарифмическое время поиска в B-Tree

Hash индекс (для точного совпадения):

# MySQL пример
CREATE TABLE users (
    id INT PRIMARY KEY,
    email VARCHAR(255),
    KEY idx_email_hash (email) USING HASH  -- Hash индекс
);

# Произвольный доступ за O(1)
SELECT * FROM users WHERE email = 'john@example.com';

Структура физического хранения

Без индекса (последовательный доступ):
Дисковые блоки:
[Запись 1][Запись 2][Запись 3]...[Запись 1000]
Для доступа к 1000-й: прочитать все 999 блоков

С B-Tree индексом (произвольный доступ):
Индекс указывает напрямую на блоки данных
    Root Node
   /    |    \
  Leaf  Leaf  Leaf  <- Каждый указывает на блок данных
  |     |     |
Данные Данные Данные

Для доступа: Root -> нужный Leaf -> нужный блок данных
Время: O(log n), обычно 2-4 операции ввода-вывода

Производительность: примеры с числами

# Таблица с 1,000,000 записей

# ПЛОХО: Последовательный доступ
# SELECT * FROM users WHERE status = 'active'
# Без индекса — нужно прочитать 1,000,000 записей
# Время: ~10 секунд (в зависимости от диска)

# ХОРОШО: Произвольный доступ через индекс
# SELECT * FROM users WHERE id = 500000
# С индексом PRIMARY KEY — только несколько операций
# Время: ~10 миллисекунд (в 1000 раз быстрее!)

# Поиск по индексированному полю
# SELECT * FROM users WHERE email = 'specific@email.com'
# С индексом — O(log n) ~ 20 операций диска
# Без индекса — O(n) ~ 1,000,000 операций

Примеры в ORM (SQLAlchemy)

from sqlalchemy import create_engine, Column, Integer, String, Index
from sqlalchemy.orm import sessionmaker
from sqlalchemy.ext.declarative import declarative_base

Base = declarative_base()

class User(Base):
    __tablename__ = 'users'
    id = Column(Integer, primary_key=True)  # Автоматический индекс
    email = Column(String(255), unique=True)  # Индекс для произвольного доступа
    username = Column(String(100))
    # Явное создание индекса
    __table_args__ = (
        Index('idx_username', 'username'),
    )

engine = create_engine('sqlite:///database.db')
Session = sessionmaker(bind=engine)
session = Session()

# БЫСТРО: произвольный доступ через индекс PRIMARY KEY
user = session.query(User).filter(User.id == 123).first()  # O(log n)

# БЫСТРО: произвольный доступ через уникальный индекс
user = session.query(User).filter(User.email == 'john@example.com').first()  # O(log n)

# МЕДЛЕННО: без индекса требуется последовательный доступ
users = session.query(User).filter(User.username.like('%john%')).all()  # O(n) full table scan

Когда использовать произвольный доступ

-- ХОРОШО: произвольный доступ
SELECT * FROM users WHERE id = 123;  -- PRIMARY KEY индекс
SELECT * FROM orders WHERE user_id = 456;  -- Индекс на foreign key
SELECT * FROM products WHERE sku = 'ABC-123';  -- Уникальный индекс

-- ПЛОХО: требуется последовательный доступ (нет индекса)
SELECT * FROM users WHERE SUBSTRING(email, 1, 3) = 'com';
SELECT * FROM orders WHERE amount > 100 AND status = 'pending';

Когда НЕ помогают индексы (требуется полное сканирование)

# Функции, препятствующие использованию индекса
SELECT * FROM users WHERE LOWER(email) = 'john@example.com';  # Функция!
SELECT * FROM users WHERE age + 5 > 25;  # Вычисление!
SELECT * FROM users WHERE email LIKE '%@gmail.com';  # Паттерн в начале

# Правильно (с индексом):
SELECT * FROM users WHERE email = 'JOHN@EXAMPLE.COM';  # Email хранится в нужном регистре
SELECT * FROM users WHERE age > 20;  # Прямое сравнение
SELECT * FROM users WHERE email LIKE 'john%';  # Паттерн в конце

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

# Индекс на несколько полей
class Order(Base):
    __tablename__ = 'orders'
    __table_args__ = (
        Index('idx_user_status', 'user_id', 'status'),
    )
    user_id = Column(Integer)
    status = Column(String(20))
    amount = Column(Float)

# БЫСТРО: оба поля из индекса
session.query(Order).filter(
    Order.user_id == 123,
    Order.status == 'completed'
).all()  # Произвольный доступ — использует индекс

# МЕДЛЕННЕЕ: второе условие вне индекса
session.query(Order).filter(
    Order.user_id == 123,
    Order.amount > 100  # Не в индексе
).all()  # Сначала индекс, потом фильтр в памяти

Анализ плана выполнения (EXPLAIN)

import sqlite3

conn = sqlite3.connect('database.db')
cursor = conn.cursor()

# БЕЗ индекса — полное сканирование таблицы
cursor.execute('EXPLAIN QUERY PLAN SELECT * FROM users WHERE email = ?', ('john@example.com',))
print(cursor.fetchall())
# Выводит: SCAN users -- полное сканирование (МЕДЛЕННО)

# С индексом — произвольный доступ
cursor.execute('CREATE INDEX idx_email ON users(email)')
cursor.execute('EXPLAIN QUERY PLAN SELECT * FROM users WHERE email = ?', ('john@example.com',))
print(cursor.fetchall())
# Выводит: SEARCH users USING INDEX idx_email -- произвольный доступ (БЫСТРО)

Вывод

Произвольный доступ в базах данных достигается через индексы (B-Tree, Hash и т.д.) и позволяет найти нужные данные за O(log n) вместо O(n). Это критически важно для производительности при работе с большими таблицами. Индексы — лучший способ оптимизировать запросы, требующие быстрого поиска по конкретным полям.