Внутренности баз данных

Зачем знать внутренности

Понимание внутренних механизмов БД позволяет:

• Проектировать эффективные схемы и запросы
• Диагностировать проблемы производительности
• Выбирать правильную БД для задачи
• Принимать обоснованные решения на System Design интервью

B-tree

B-tree (и его вариант B+ tree) -- основная структура данных для индексов в реляционных БД (PostgreSQL, MySQL).

Структура B+ tree

                    ┌─────────────┐
                    │   [30, 70]  │  Root
                    └──┬───┬───┬──┘
                       │   │   │
          ┌────────────┘   │   └────────────┐
          ▼                ▼                ▼
    ┌──────────┐    ┌──────────┐    ┌──────────┐
    │ [10, 20] │    │ [40, 50] │    │ [80, 90] │  Internal
    └─┬──┬──┬──┘    └─┬──┬──┬──┘    └─┬──┬──┬──┘  Nodes
      │  │  │         │  │  │         │  │  │
      ▼  ▼  ▼         ▼  ▼  ▼         ▼  ▼  ▼
    [5,8][12,15][22,28][35,38][45,48][55,65][75,78][85,88][92,99]
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                        Leaf Nodes (data pointers)
                        Linked list ←→ for range scans

Свойства B+ tree

<?php

declare(strict_types=1);

/**
 * B-tree behavior impact on query performance
 */
final class BTreeBehavior
{
    public function __construct(
        private readonly \PDO $db,
    ) {}

    /**
     * B-tree efficient: equality and range on indexed column
     * PostgreSQL does 3-4 page reads to find the row
     */
    public function efficientBTreeQuery(): void
    {
        // Point lookup: O(log N) -- 3-4 I/O
        $this->db->query("SELECT * FROM users WHERE id = 12345");

        // Range scan: find start in O(log N), then follow leaf links
        $this->db->query("SELECT * FROM users WHERE id BETWEEN 100 AND 200");

        // Prefix search uses B-tree
        $this->db->query("SELECT * FROM users WHERE name LIKE 'John%'");
    }

    /**
     * B-tree INefficient: these cannot use standard B-tree index
     */
    public function inefficientBTreeQuery(): void
    {
        // Function on indexed column: can't use index
        $this->db->query("SELECT * FROM users WHERE LOWER(email) = '[email protected]'");
        // Fix: functional index CREATE INDEX idx ON users (LOWER(email))

        // Leading wildcard: can't use B-tree
        $this->db->query("SELECT * FROM users WHERE name LIKE '%john%'");
        // Fix: use GIN index with trigrams or full-text search

        // OR with different columns: usually seq scan
        $this->db->query("SELECT * FROM users WHERE name = 'John' OR email = '[email protected]'");
        // Fix: use UNION or bitmap index scan
    }

    /**
     * Composite index: column order matters!
     */
    public function compositeIndexBehavior(): void
    {
        // Index: (country, city, zip_code)

        // Uses full index (leftmost prefix)
        $this->db->query("SELECT * FROM addresses WHERE country = 'RU' AND city = 'Moscow' AND zip_code = '101000'");

        // Uses first 2 columns of index
        $this->db->query("SELECT * FROM addresses WHERE country = 'RU' AND city = 'Moscow'");

        // Uses first column only
        $this->db->query("SELECT * FROM addresses WHERE country = 'RU'");

        // CANNOT use index (skips leftmost column)
        $this->db->query("SELECT * FROM addresses WHERE city = 'Moscow'");
    }
}

LSM-tree (Log-Structured Merge-tree)

LSM-tree используется в Cassandra, RocksDB, LevelDB, ClickHouse. Оптимизирован для записи.

Как работает LSM-tree

Write path:

1. Write to WAL (disk) ─────────────────────────> Crash safety
2. Write to MemTable (RAM, sorted) ─────────────> Fast writes
3. When MemTable full → flush to SSTable (disk) ─> Sorted file
4. Background compaction merges SSTables ────────> Optimization

Read path:

1. Check MemTable (RAM) ─────> Found? Return
2. Check Bloom filters ──────> Skip SSTables that don't have key
3. Check SSTables (newest first) → Read from disk

┌────────────┐
│  MemTable  │  (RAM, sorted)
│  (Red-Black│
│   Tree)    │
└─────┬──────┘
      │ flush when full
      ▼
┌─────────────┐  ┌─────────────┐  ┌─────────────┐
│  SSTable L0 │  │  SSTable L0 │  │  SSTable L0 │  Level 0
│  (sorted)   │  │  (sorted)   │  │  (sorted)   │  (may overlap)
└──────┬──────┘  └──────┬──────┘  └──────┬──────┘
       │                │                │
       └────────────────┼────────────────┘
                        │ compaction
                        ▼
       ┌─────────────────────────────────┐
       │         SSTable Level 1         │  Level 1
       │  (sorted, non-overlapping)      │  (no overlaps)
       └────────────────┬────────────────┘
                        │ compaction
                        ▼
       ┌─────────────────────────────────┐
       │         SSTable Level 2         │  Level 2
       │  (sorted, non-overlapping)      │  (larger)
       └─────────────────────────────────┘

B-tree vs LSM-tree

WAL (Write-Ahead Log)

WAL обеспечивает durability: сначала записываем изменение в журнал, потом применяем к данным.

Transaction: UPDATE balance = 1000 WHERE id = 5

Step 1: Write to WAL (sequential write, fast)
        ┌─────────────────────────────────────┐
   WAL: │ LSN=100: UPDATE users SET balance=  │
        │ 1000 WHERE id=5 [tx_id=42]          │
        └─────────────────────────────────────┘

Step 2: Update in Buffer Pool (RAM)
        Memory page for users table updated

Step 3: Eventually flush dirty page to disk
        (checkpoint)

Crash Recovery:
  1. Read WAL from last checkpoint
  2. Replay committed transactions
  3. Undo uncommitted transactions

<?php

declare(strict_types=1);

/**
 * Understanding WAL impact on application design
 */
final class WalAwareness
{
    public function __construct(
        private readonly \PDO $db,
    ) {}

    /**
     * synchronous_commit controls WAL durability
     */
    public function configureDurability(): void
    {
        // Maximum durability (default): WAL flushed to disk on commit
        $this->db->exec("SET synchronous_commit = 'on'");

        // Faster commits, but last few ms of data may be lost on crash
        // Good for: logging, analytics, non-critical data
        $this->db->exec("SET synchronous_commit = 'off'");
    }

    /**
     * Batch operations reduce WAL overhead
     */
    public function batchInsert(array $records): void
    {
        // Bad: 1000 individual commits = 1000 WAL flushes
        // Good: 1 transaction = 1 WAL flush
        $this->db->beginTransaction();

        $stmt = $this->db->prepare(
            'INSERT INTO logs (message, level, created_at) VALUES (:msg, :level, NOW())'
        );

        foreach ($records as $record) {
            $stmt->execute(['msg' => $record['message'], 'level' => $record['level']]);
        }

        $this->db->commit(); // Single WAL flush for all inserts
    }
}

Buffer Pool

Buffer Pool -- область памяти, где БД кэширует страницы данных и индексов:

┌─────────────────────────────────────┐
│           Buffer Pool (RAM)         │
│                                     │
│  ┌──────┐ ┌──────┐ ┌──────┐       │
│  │Page 1│ │Page 5│ │Page 9│  ...   │  Hot pages
│  │(clean)│ │(dirty)│ │(clean)│       │  cached
│  └──────┘ └──────┘ └──────┘       │
│                                     │
│  LRU / Clock replacement policy    │
│  Hit ratio target: > 99%           │
└─────────────────────────────────────┘
         ↕ read/write
┌─────────────────────────────────────┐
│              Disk                   │
│  [Page 1][Page 2][Page 3]...       │
└─────────────────────────────────────┘

<?php

declare(strict_types=1);

/**
 * Monitor buffer pool performance
 */
final class BufferPoolMonitor
{
    public function __construct(
        private readonly \PDO $db,
    ) {}

    /**
     * PostgreSQL: check buffer cache hit ratio
     */
    public function getHitRatio(): array
    {
        return $this->db->query(<<<SQL
            SELECT
                datname,
                blks_hit,
                blks_read,
                CASE WHEN blks_hit + blks_read = 0 THEN 0
                     ELSE round(blks_hit::numeric / (blks_hit + blks_read) * 100, 2)
                END as hit_ratio_pct
            FROM pg_stat_database
            WHERE datname = current_database()
        SQL)->fetch(\PDO::FETCH_ASSOC);
        // Target: > 99% hit ratio
    }

    /**
     * Find tables that don't fit in buffer pool
     */
    public function getTableCacheStats(): array
    {
        return $this->db->query(<<<SQL
            SELECT
                relname as table_name,
                pg_size_pretty(pg_relation_size(relid)) as table_size,
                heap_blks_hit as cache_hits,
                heap_blks_read as disk_reads,
                CASE WHEN heap_blks_hit + heap_blks_read = 0 THEN 0
                     ELSE round(heap_blks_hit::numeric / (heap_blks_hit + heap_blks_read) * 100, 2)
                END as hit_ratio_pct
            FROM pg_statio_user_tables
            ORDER BY heap_blks_read DESC
            LIMIT 20
        SQL)->fetchAll(\PDO::FETCH_ASSOC);
    }
}

Query Optimizer

Query optimizer выбирает оптимальный план выполнения запроса из множества возможных:

Этапы оптимизации

SQL Query
    │
    ▼
┌──────────┐
│  Parser  │  → AST (Abstract Syntax Tree)
└────┬─────┘
     │
     ▼
┌──────────┐
│ Rewriter │  → Simplification, view expansion
└────┬─────┘
     │
     ▼
┌──────────┐
│Optimizer │  → Cost-based optimization
│          │    - Table statistics
│          │    - Index availability
│          │    - Join ordering
│          │    - Access method selection
└────┬─────┘
     │
     ▼
┌──────────┐
│ Executor │  → Execute optimal plan
└──────────┘

<?php

declare(strict_types=1);

/**
 * Working with query optimizer
 */
final class QueryOptimizerInsights
{
    public function __construct(
        private readonly \PDO $db,
    ) {}

    /**
     * EXPLAIN ANALYZE: see actual execution plan
     */
    public function analyzeQuery(string $sql): array
    {
        $result = $this->db->query(
            "EXPLAIN (ANALYZE, BUFFERS, FORMAT JSON) " . $sql
        )->fetchColumn();

        $plan = json_decode($result, true);

        return [
            'plan' => $plan[0]['Plan'],
            'execution_time_ms' => $plan[0]['Execution Time'],
            'planning_time_ms' => $plan[0]['Planning Time'],
        ];
    }

    /**
     * Statistics: optimizer needs fresh stats
     */
    public function updateStatistics(string $tableName): void
    {
        // Analyze updates table statistics for optimizer
        $this->db->exec("ANALYZE {$tableName}");
    }

    /**
     * Common performance issues and fixes
     */
    public function commonIssues(): array
    {
        return [
            'seq_scan_on_large_table' => [
                'cause' => 'Missing index or outdated statistics',
                'fix' => 'CREATE INDEX or ANALYZE table',
            ],
            'nested_loop_on_large_join' => [
                'cause' => 'Missing index on join column',
                'fix' => 'CREATE INDEX on FK columns',
            ],
            'sort_on_disk' => [
                'cause' => 'work_mem too small for sort',
                'fix' => 'Increase work_mem or add covering index',
            ],
            'bitmap_heap_scan_lossy' => [
                'cause' => 'work_mem too small for bitmap',
                'fix' => 'Increase work_mem',
            ],
        ];
    }
}

Итоги

• B-tree -- сбалансированное дерево для быстрых reads, используется в PostgreSQL/MySQL
• LSM-tree -- append-only структура для быстрых writes, используется в Cassandra/RocksDB
• WAL -- журнал предзаписи, обеспечивает durability через sequential writes
• Buffer Pool -- кэш страниц в памяти, целевой hit ratio > 99%
• Query Optimizer -- выбирает план на основе статистики; EXPLAIN ANALYZE -- инструмент диагностики
• Понимание внутренностей помогает проектировать эффективные схемы и диагностировать проблемы