Какими структурами данных может быть представлен индекс

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

Индекс — это структура данных, которая позволяет быстро находить данные по ключу или значению. В контексте базы данных и приложений Go используются разные структуры.

1. Hash Table (Хеш-таблица)

Наиболее распространённая структура для индексов:

// Пример: Go map работает как хеш-таблица
type Index map[string]uint64

var userIndex Index = make(map[string]uint64)
userIndex["john@example.com"] = 12345 // O(1) поиск

// В БД: CREATE INDEX idx_email ON users(email) USING HASH

Характеристики:

• Временная сложность: O(1) в среднем, O(n) в худшем случае (коллизии)
• Пространственная сложность: O(n)
• Использование: Поиск по точному значению
• Минусы: Нет поддержки range queries

2. B-Tree (B-дерево)

Самая популярная структура в БД (PostgreSQL, MySQL, SQLite):

         [30]
       /      \
    [10,20]   [40,50]
    /  |  \\    /  |  \\
  [5] [15][25][35][45][55]

Характеристики:

• Временная сложность: O(log n) для поиска
• Пространственная сложность: O(n)
• Использование: Поиск, range queries, сортировка
• Преимущества: Хорошая локальность памяти, кэшируется на диске
• Применение: CREATE INDEX idx_id ON users(id) — по умолчанию BTREE

// Пример в Go: структура B-дерева
type BNode struct {
    Keys     []int
    Children []*BNode
    IsLeaf   bool
}

// Поиск: O(log n)
func (n *BNode) Search(key int) bool {
    // бинарный поиск + рекурсия
}

3. Hash Index vs B-Tree Index в PostgreSQL

-- Hash Index: быстрый поиск по точному значению
CREATE INDEX idx_hash ON users USING HASH(email);
SELECT * FROM users WHERE email = "john@example.com"; -- O(1)

-- B-Tree Index: поддерживает range queries
CREATE INDEX idx_btree ON users USING BTREE(age);
SELECT * FROM users WHERE age > 18 AND age < 65; -- O(log n)

4. Inverted Index (Обратный индекс)

Для полнотекстового поиска (Elasticsearch, PostgreSQL FTS):

Документ 1: "Go is fast"
Документ 2: "Go is simple"

Индекс:
"Go"     → [1, 2]
"is"     → [1, 2]
"fast"   → [1]
"simple" → [2]

type InvertedIndex map[string][]int

func (idx InvertedIndex) Search(word string) []int {
    return idx[word] // Быстрый поиск всех документов со словом
}

5. Bitmap Index

Для низкокардинальных данных (статус, флаги):

Status  Bitmap
Active  10101011
Inactive 01010100

Поиск активных пользователей: O(n/8) байт

// В Go: bitset
var active [1000]bool
for i := 0; i < 1000; i++ {
    if active[i] {
        // активный пользователь
    }
}

6. R-Tree (пространственные индексы)

Для геоданных, координат:

        ┌────────────────┐
        │    Root        │
        ├────────┬───────┤
    ┌───┴─┐   ┌─┴──┐
    │North│   │South│
    └─────┘   └────┘

type GeoIndex struct {
    // Структура для хранения географических данных
    BoundingBox struct {
        MinLat, MaxLat float64
        MinLon, MaxLon float64
    }
}

// Поиск всех объектов в прямоугольнике: O(log n)

Сравнительная таблица