Где хранится B-tree?

Question

claude-haiku-4.5 · Accepted Answer

## Где хранится B-tree

B-tree (B-дерево) — это самораспределяющееся сбалансированное дерево поиска, оптимизированное для работы с дисковой памятью. Оно хранится **на диске в базах данных**, а не в оперативной памяти.

## Хранилище B-tree

### 1. В базах данных (основное место)

B-tree используется для хранения индексов и данных в большинстве СУБД:

#### PostgreSQL

B-tree индексы хранятся в файлах данных PostgreSQL:

```sql
-- Создание B-tree индекса (по умолчанию)
CREATE INDEX idx_users_email ON users(email);

-- Просмотр информации об индексе
SELECT * FROM pg_indexes WHERE tablename = "users";

-- Проверка размера индекса на диске
SELECT pg_size_pretty(pg_relation_size("idx_users_email"));
```

Файлы хранятся в:
```
$PGDATA/base/[database_oid]/[index_oid]
```

#### MySQL / InnoDB

B+ tree (вариант B-tree) используется для первичных и вторичных индексов:

```sql
-- InnoDB использует B+ tree по умолчанию
CREATE TABLE users (
    id INT PRIMARY KEY,  -- B+ tree для primary key
    email VARCHAR(255) UNIQUE  -- B+ tree для unique index
);

-- Просмотр информации об индексах
SHOW INDEX FROM users;
```

Файлы хранятся в:
```
data/database_name/table_name.ibd
```

#### SQLite

B-tree структура встроена непосредственно в файл БД:

```python
import sqlite3

conn = sqlite3.connect("database.db")  # Это обычный файл на диске
cursor = conn.cursor()

# Создание индекса B-tree
cursor.execute("CREATE INDEX idx_users_email ON users(email)")
conn.commit()
```

Весь B-tree хранится в одном файле `database.db` на диске.

### 2. Структура хранения на диске

B-tree разделен на **блоки (pages)** одинакового размера, обычно 4KB или 8KB:

```
Disk File (index_oid)
┌────────────────┐
│ Root Page      │  ← корневой узел B-tree
├────────────────┤
│ Internal Page  │  ← промежуточные узлы
├────────────────┤
│ Internal Page  │
├────────────────┤
│ Leaf Page      │  ← листовые узлы (содержат данные/поinters)
├────────────────┤
│ Leaf Page      │
├────────────────┤
│ Free Space     │
└────────────────┘
```

Каждая страница содержит:
- Заголовок (metadata, количество записей)
- Ключи и указатели на дочерние страницы
- Данные (для листовых узлов)

### 3. Процесс работы B-tree при поиске

```python
# Пример: поиск записи email=alice@example.com в индексе

# 1. СУБД читает Root Page с диска (блок поиска O(1))
# 2. Находит диапазон ключей, куда входит alice@...
# 3. Читает Internal Page (следующий уровень B-tree)
# 4. Повторяет до Leaf Page
# 5. Находит точное значение на листе

# Все это требует несколько дисковых операций (обычно 3-4 для миллионов записей)
```

## Почему B-tree на диске?

### 1. Оптимизация для дисковых операций

B-tree специально разработано для минимизации количества дисковых обращений:

```python
# Характеристики B-tree:
# - Высокий коэффициент ветвления (обычно 100-200 указателей в узле)
# - Каждый узел размером ~ 4KB (размер блока на диске)
# - Высота дерева ~ log_n(количество_записей)

# Для 1 миллиона записей:
# - Высота B-tree ~ 3-4 уровня
# - Количество дисковых обращений ~ 3-4
```

### 2. Сравнение со сбалансированным бинарным деревом

```
Бинарное дерево (для 1 млн записей):
- Высота ~ 20
- Дисковых обращений ~ 20 (очень медленно!)

B-tree (для 1 млн записей):
- Высота ~ 3
- Дисковых обращений ~ 3 (быстро!)
```

### 3. Локальность данных (Cache Locality)

Вся информация узла размещается в одном блоке на диске:

```
Likelihood of cache hits increased because all child pointers are in one disk block
┌─ Disk Block (4KB) ──────────────┐
│ ┌─Key1──┐┌─Key2──┐┌─Key3──┐    │
│ │Ptr_L  ││Ptr_M  ││Ptr_R  │    │  All loaded once!
│ └───────┘└───────┘└───────┘    │
└────────────────────────────────┘
```

## Как СУБД управляет B-tree на диске

### Буффер пул (Buffer Pool)

СУБД кэширует часто используемые страницы B-tree в памяти:

```python
# PostgreSQL
shared_buffers = 256MB  # Размер буффер пула

# MySQL
innodb_buffer_pool_size = 1GB

# SQLite
page_cache_size = 100000  # Количество страниц в памяти
```

Процесс:
1. Запрос приходит в СУБД
2. СУБД проверяет, есть ли нужная страница B-tree в буффер пуле
3. Если есть → читает из памяти (O(1) микросекунд)
4. Если нет → читает с диска в буффер пул (O(1-10) миллисекунд)

### Пример работы буффер пула

```python
# Первый SELECT (cache miss)
SELECT * FROM users WHERE email = alice@example.com;
# B-tree поиск требует 3 дисковых обращения: 10ms

# Второй SELECT (cache hit)
SELECT * FROM users WHERE email = alice@example.com;
# Страницы B-tree уже в памяти: 0.01ms

# Сотый SELECT (cache hit)
SELECT * FROM users WHERE email = alice@example.com;
# Полностью из кэша: 0.01ms
```

## Модификация B-tree на диске

### Вставка новых записей

Когда листовой узел переполняется:

```
До вставки:
┌──────────┐
│ Leaf     │  ← node full (16 записей из 16 max)
└──────────┘

После вставки:
┌──────────┬──────────┐
│ Leaf 1   │ Leaf 2   │  ← node split
└──────────┴──────────┘
     ↓
   root page обновляется
```

```python
# Код B-tree вставки (упрощённо)
def insert(key, value):
    leaf_page = find_leaf_page(key)
    leaf_page.insert(key, value)
    
    if leaf_page.is_full():
        split_leaf_page(leaf_page)
        # Записать обновлённые страницы на диск
        disk.write(leaf_page)
        if parent.is_full():
            split_parent()  # Каскадное разделение
```

### Удаление записей

```sql
-- Удаление влияет на структуру B-tree
DELETE FROM users WHERE email = alice@example.com;

-- Если узел становится недоиспользуемым
-- СУБД может объединить его с соседним узлом
```

## Файловая система и B-tree

Даже файловые системы используют B-tree:

### ext4 / NTFS / APFS

```bash
# На уровне файловой системы используется B-tree структура
# для хранения метаданных файлов и директорий

# ext4 использует extents (последовательные блоки)
# NTFS использует B+ tree для MFT (Master File Table)
```

## Оптимизация B-tree на диске

### 1. Выбор размера узла (page size)

```sql
-- В PostgreSQL (по умолчанию 8KB)
-- В MySQL (по умолчанию 16KB)
-- В SQLite (по умолчанию 4KB)

-- Меньше страница → больше обращений к диску
-- Больше страница → больше памяти занимает
```

### 2. FILLFACTOR для PostgreSQL

```sql
-- Оставить место для обновлений без разделения
CREATE INDEX idx_users ON users(email) WITH (fillfactor = 70);
```

### 3. Регулярное переиндексирование

```sql
-- PostgreSQL
REINDEX INDEX idx_users;

-- MySQL
OPTIMIZE TABLE users;
```

## Вывод

B-tree хранится **на диске в файлах базы данных**, разделённое на блоки (pages) размером 4-8KB. СУБД кэширует часто используемые страницы в памяти (buffer pool) и управляет всей структурой для оптимального баланса между скоростью поиска (логарифмическое время) и количеством дисковых обращений (обычно 3-4 для миллионов записей).

Где хранится B-tree?

Комментарии (1)

Где хранится B-tree

Хранилище B-tree

1. В базах данных (основное место)

PostgreSQL

MySQL / InnoDB

SQLite

2. Структура хранения на диске

3. Процесс работы B-tree при поиске

Почему B-tree на диске?

1. Оптимизация для дисковых операций

2. Сравнение со сбалансированным бинарным деревом

3. Локальность данных (Cache Locality)

Как СУБД управляет B-tree на диске

Буффер пул (Buffer Pool)

Пример работы буффер пула

Модификация B-tree на диске

Вставка новых записей

Удаление записей

Файловая система и B-tree

ext4 / NTFS / APFS

Оптимизация B-tree на диске

1. Выбор размера узла (page size)

2. FILLFACTOR для PostgreSQL

3. Регулярное переиндексирование

Вывод