102 lines
5.1 KiB
Markdown
102 lines
5.1 KiB
Markdown
# ⚙️ Storage enginy a transakční modely
|
|
|
|
## B-Tree vs LSM-Tree
|
|
|
|
Dva dominantní storage engine přístupy v moderních databázích.
|
|
|
|
| Vlastnost | B-Tree | LSM-Tree |
|
|
|-----------|--------|----------|
|
|
| **Zápis** | In-place update (náhodný I/O na page) | Append-only (sekvenční I/O) |
|
|
| **Čtení** | Rychlé (přímo v page, O(log N)) | Pomalejší (merge z více SSTable, bloom filtry) |
|
|
| **Write amplification** | Nižší (přepis stránky) | Vyšší (kompakce, merge SSTables) |
|
|
| **Read amplification** | Nižší (1 page read) | Vyšší (více SSTable k prohledání) |
|
|
| **Komprese** | Horší (fragmentace page) | Lepší (kompaktní SSTable, bloková komprese) |
|
|
| **Range scan** | Rychlý (linked list na listové úrovni) | Rychlý (SSTable jsou seřazené) |
|
|
| **Space amplification** | Nízká | Vyšší (čeká na kompakci) |
|
|
| **Typické DB** | PostgreSQL, MySQL (InnoDB), SQLite, Oracle | Cassandra, RocksDB, LevelDB, ScyllaDB, MongoDB (WiredTiger) |
|
|
|
|
### Kdy zvolit který engine
|
|
|
|
**B-Tree** — když:
|
|
- Potřebujete rychlé point lookupy (PK lookup, jedinečné ID)
|
|
- Workload je read-heavy (většina dotazů = SELECT podle klíče)
|
|
- Potřebujete range dotazy na primárním klíči
|
|
- Transakční workload (OLTP) s krátkými dotazy
|
|
|
|
**LSM-Tree** — když:
|
|
- Potřebujete vysokou propustnost zápisů (write-heavy)
|
|
- Append-only workload (logy, time-series, IoT)
|
|
- Komprese dat je důležitá (ušetří místo)
|
|
- Write amplification nevadí (dostatek I/O kapacity)
|
|
|
|
## Write-Ahead Log (WAL)
|
|
|
|
Append-only log garantující, že žádná operace není ztracena při crash:
|
|
|
|
```text
|
|
1. Transaction BEGIN → záznam do WAL
|
|
2. Data modification → záznam do WAL (před modifikací page)
|
|
3. Transaction COMMIT → flush WAL na disk (COMMIT potvrzen až po flush)
|
|
4. Checkpoint → flush dirty pages → WAL do bodu checkpointu může být smazán
|
|
```
|
|
|
|
- **Write-ahead** — WAL zapsán dříve než data page
|
|
- **Checkpoint** — bod, odkud je WAL při recovery potřeba
|
|
- **Redo log** (InnoDB) — podobný koncept, slouží k přehrání chybějících změn
|
|
- **Group commit** — více transakcí flushne WAL najednou (vyšší propustnost)
|
|
|
|
## MVCC (Multi-Version Concurrency Control)
|
|
|
|
Každá transakce vidí snapshot dat v okamžiku startu. Staré verze řádků zůstávají v tabulce.
|
|
|
|
### Implementace
|
|
|
|
| DB | Mechanismus | Vacuum/GC | Izolační úrovně |
|
|
|----|------------|-----------|-----------------|
|
|
| **PostgreSQL** | Heap tuple (xmin/xmax) — staré verze v hlavní tabulce | VACUUM (autovacuum) | RU, RC, RR, Serializable (SSI) |
|
|
| **MySQL InnoDB** | Undo log — staré verze v undo segmentech | Purge (automatický) | RU, RC, RR, Serializable |
|
|
| **MSSQL** | Tempdb version store | Automatické (row versioning) | RC (snapshot), Serializable |
|
|
| **Oracle** | Undo tablespace | Automatické (undo retention) | RC, Serializable, Read-only |
|
|
| **MongoDB WiredTiger** | MVCC na úrovni dokumentu | Automatické (eviction) | Snapshot isolation |
|
|
| **Cassandra** | MVCC není (přepis valore) | Compaction (merge SSTable) | — |
|
|
|
|
### Anomálie
|
|
|
|
| Úroveň | Dirty Read | Non-repeatable Read | Phantom Read | Serialization Anomaly |
|
|
|--------|-----------|---------------------|-------------|----------------------|
|
|
| **Read Uncommitted** | Ano | Ano | Ano | Ano |
|
|
| **Read Committed** | Ne | Ano | Ano | Ano |
|
|
| **Repeatable Read** | Ne | Ne | Ne (PG: ne, MySQL: next-key locking) | Ano |
|
|
| **Serializable** | Ne | Ne | Ne | Ne |
|
|
|
|
- **Dirty Read** — čtení dat z necommitnuté transakce
|
|
- **Non-repeatable Read** — stejný dotaz vrátí jiná data
|
|
- **Phantom Read** — stejný dotaz vrátí nové řádky
|
|
- **Serialization Anomaly** — výsledek transakcí není ekvivalentní žádnému sériovému pořadí
|
|
|
|
## Index types
|
|
|
|
| Typ | Algoritmus | Use case | DB podpora |
|
|
|-----|-----------|----------|------------|
|
|
| **B-tree** | Balanced tree | `=`, `<`, `>`, `BETWEEN`, `IN`, `LIKE (prefix)` | Všechny (výchozí) |
|
|
| **Hash** | Hash table | Pouze `=` (equality) | PostgreSQL (hash index), MySQL (MEMORY) |
|
|
| **GiST** | Generalized Search Tree | Geometrie, full-text, intervaly, IP rozsahy | PostgreSQL |
|
|
| **GIN** | Generalized Inverted Index | JSONB, pole, full-text (contains, overlaps) | PostgreSQL |
|
|
| **BRIN** | Block Range Index | Time-series, logy (data v pořadí) — extrémně malý | PostgreSQL |
|
|
| **SP-GiST** | Space-partitioned | Kvadranty, KD-tree, radix tree | PostgreSQL |
|
|
| **R-tree** | Prostorový strom | Geoprostorová data | MySQL (MyISAM/InnoDB), SQLite |
|
|
| **Clustered index** | B-tree + data v listech | PK lookup (InnoDB) — data uložena s indexem | MySQL InnoDB, MSSQL |
|
|
| **Full-text** | Inverted index | Text search (stemming, relevance) | MySQL, PostgreSQL, MSSQL |
|
|
|
|
## Zdroje
|
|
|
|
Odkazy, knihy a standardy: [sources/databases/sources.md](sources/databases/sources.md)
|
|
|
|
### Doporučená literatura
|
|
|
|
| Kniha | Autoři | ISBN | Popis |
|
|
|-------|--------|------|-------|
|
|
| Database Internals | Alex Petrov | 978-1492040346 | Hloubkový výklad storage engine (B-Tree, LSM-Tree, WAL, MVCC), distribuované systémy (partitioning, replication, consensus) |
|
|
|
|
*Poslední revize: 2026-06-03*
|