--- title: "Дълбоко гмуркане в индексите на бази данни: как работи под капака" description: "Подробно ръководство за разработчици за B+Tree в InnoDB, купища (Heap) в Postgres, указатели на листови възли, правила за съставни индекси, разширени видове индекси и излишно записване (write amplification)." published: 2026-05-31 faq: - question: "Защо InnoDB използва клъстериран индекс, докато Postgres използва структура тип купчина (Heap)?" answer: "InnoDB съхранява данните на редовете директно в листовите възли на B+Tree на първичния ключ, за да направи търсенето по първичен ключ изключително бързо и да запази свързаните данни последователни. Postgres съхранява всички данни в купчина (Heap) файл и прави всички индекси (включително първичния ключ) вторични, които сочат към местоположения в купчината чрез TID. Това опростява преместването на редове при актуализации и избягва двойно търсене за вторични индекси, но изисква посещение на купчината при заявки по първичен ключ." - question: "Какво е GIN индекс и кога трябва да го използвам в Postgres?" answer: "Обобщеният инвертиран индекс (GIN) е предназначен за индексиране на съставни стойности като JSONB или масиви. Той картографира отделните елементи (ключове или стойности) към съответните им TID, което позволява изключително ефективно изпълнение на заявки с оператори като `@>` (съдържа) или `?` (има ключ)." - question: "Как се получава излишно записване (write amplification) при поддръжка на индекси?" answer: "Излишното записване възниква, защото всяка операция INSERT, UPDATE или DELETE изисква от базата данни да актуализира както данните в таблицата, така и всички свързани индекси. Освен това, ако вмъкването попадне в пълна B-Tree страница, страницата трябва да бъде разделена (Page Split), което води до записване на множество страници на диска и фрагментация." - question: "Как мога да избегна двойно търсене във вторичните индекси под InnoDB?" answer: "За да избегнете двойно търсене (сканиране на вторичния индекс, последвано от търсене в клъстерирания индекс по първичен ключ), можете да създадете покриващ индекс (Covering Index), който съдържа всички колони, изисквани от SELECT заявката. Така базата данни ще получи данните директно от вторичния индекс." --- # Дълбоко гмуркане в индексите на бази данни: как работи под капака Всяка заявка към база данни, която пишете, е състезание с дисковия входно-изходен процес (I/O). Когато вашият набор от данни се побира в оперативната памет (RAM), заявките са мигновени. Но когато данните ви нараснат до милиони редове и излязат на диска, вашата база данни трябва или да претърси всяка една страница на диска (последователно сканиране), или да използва карта, за да скочи директно до нужните данни. Тази карта е индексът. Разбирането на това как работят индексите на ниво диск и страници отличава младшите разработчици, които произволно добавят индекси към таблиците, от архитектите на бази данни, които проектират самооптимизиращи се и високопроизводителни системи за съхранение. В това дълбоко гмуркане ще премахнем слоя на абстракция на MySQL (InnoDB) и PostgreSQL, за да видим как те представят индексите на диска, как се решава редът на съставните колони и реалната цена на излишното записване (write amplification). --- ## 1. Под капака: B+Tree в InnoDB срещу Heap & B-Tree в Postgres Базите данни не съхраняват таблиците като прости масиви от редове. Те ги структурират на диска с помощта на страници (обикновено 16KB в InnoDB, 8KB в PostgreSQL). Архитектурите им за съхранение обаче са фундаментално различни. ### InnoDB: Клъстерираният индекс (B+Tree) В енджина InnoDB на MySQL **самата таблица е индексът**. По-конкретно, таблицата е структурирана като B+Tree, изградено около първичния ключ (Primary Key). Това се нарича **клъстериран индекс**. * **Вътрешни възли (Internal Nodes):** Съдържат само ключове и указатели към дъщерни страници. Те насочват енджина по време на търсене. * **Листови възли (Leaf Nodes):** Съдържат самите редове с данни. Листовите страници са свързани последователно в двусвързан списък, което прави сканирането на диапазони (`WHERE id BETWEEN 10 AND 50`) изключително бързо. * **Вторични индекси (Secondary Indexes):** Всеки индекс, различен от първичния ключ в InnoDB, е вторичен. Листовите възли на вторичния индекс *не* сочат към физически дискови адреси. Вместо това те съхраняват **стойността на първичния ключ** за съответния ред. > [!NOTE] > Тъй като вторичните индекси в InnoDB съхраняват първичния ключ, търсенето на ред чрез вторичен индекс (например `WHERE email = 'user@example.com'`) изисква търсене в две стъпки: първо, преминаване през вторичния индекс за намиране на първичния ключ, и второ, преминаване през B+Tree на клъстерирания индекс за извличане на данните от реда. ``` [Вторичен индекс (Email)] Листов възел: 'user@example.com' -> PK: 42 | v [Клъстериран индекс (ID)] Листов възел: PK: 42 -> Данни на реда: {id: 42, email: 'user@example.com', name: 'John Doe'} ``` ### PostgreSQL: Купчина (Heap) и B-Tree PostgreSQL не използва клъстерирани индекси по подразбиране. Вместо това той съхранява данните от редовете в неструктуриран вид, наречен **Купчина (Heap)**. * **Страници на купчината (Heap Pages):** Редовете на таблицата се добавят в страниците в реда на тяхното вмъкване (или там, където има свободно място). * **B-Tree индекси:** Всеки индекс в Postgres (включително първичният ключ) е вторичен индекс. * **Листови възли (Leaf Nodes):** Листовите възли на B-Tree индекс в Postgres съдържат **идентификатор на кортеж (TID)**, който е физически адрес на диска, състоящ се от номер на блок (страница) и индекс на отместване в рамките на тази страница (например `(Page 14, Offset 3)`). > [!WARNING] > Тъй като индексите на Postgres съхраняват физически TID, всяка операция, която премества ред на диска (например UPDATE, който променя размера на реда, или MVCC миграция на страници), би счупила тези TID. Postgres управлява това чрез процеси на почистване (vacuum) и оптимизация HOT (Heap Only Tuples), но това означава, че всички индекси сочат директно към Heap. ``` [Индекс Postgres (Email)] [Купчина Postgres (Heap - неподредена)] Лист: 'user@example.com' -> TID: (Page 14, Offset 3) ----> Page 14, Slot 3: {id: 42, ...} ``` --- ## 2. Правила за ред на колоните в съставен индекс При създаване на индекс върху множество колони — **съставен индекс (composite index)** — редът на колоните в дефиницията е от критично значение. Грешният ред на колоните ще направи индекса напълно неизползваем за определени заявки. Златните правила за проектиране на съставен индекс са: 1. **Правило за най-левия префикс (Leftmost Prefix Rule):** Базата данни може да използва съставен индекс само ако заявката първо филтрира по най-лявата колона от индекса. Индекс върху `(A, B, C)` може да оптимизира заявки, филтриращи по `(A)`, `(A, B)` и `(A, B, C)`, но *не* може да оптимизира заявки, филтриращи само по `(B)` или `(C)`. 2. **Първо равенство, накрая диапазон (Equality First, Range Last):** Колоните, филтрирани с точно равенство (`=`, `IN`), трябва да са първи в индекса. Колоните, филтрирани с диапазони (`<`, `>`, `BETWEEN`, `LIKE`), трябва да са накрая. След като се оцени диапазонна колона, базата данни не може да използва следващите колони в индекса за филтриране. 3. **Висока кардиналност на първо място (High Cardinality First):** Колоните с висока кардиналност (много уникални стойности, напр. `user_id`) обикновено трябва да предхождат колоните с ниска кардиналност (малко уникални стойности, напр. `status`), при условие че и двете се търсят с равенство. Нека разгледаме конкретна миграция и заявка: ```sql -- database/migrations/2026_05_31_create_orders_table.sql CREATE TABLE orders ( id BIGINT AUTO_INCREMENT PRIMARY KEY, user_id BIGINT NOT NULL, status VARCHAR(50) NOT NULL, amount DECIMAL(10, 2) NOT NULL, created_at TIMESTAMP NOT NULL ); -- database/migrations/2026_05_31_add_composite_index.sql -- Оптимален индекс за: user_id (равенство) + status (равенство) + created_at (диапазон/сортиране) CREATE INDEX idx_orders_user_status_created ON orders (user_id, status, created_at); ``` За заявката по-долу индексът позволява на енджина веднага да филтрира по `user_id`, след това по `status` и след това да прочете предварително сортираните стойности на `created_at` в обратен ред, без да е необходима отделна операция filesort. ```sql -- database/queries/find_user_orders.sql SELECT id, user_id, status, created_at, amount FROM orders WHERE user_id = 42 AND status = 'completed' ORDER BY created_at DESC LIMIT 10; ``` --- ## 3. Дълбоко гмуркане в типовете индекси Различните шаблони на заявки изискват различни структури от данни. Ето сравнение на типовете индекси, налични в MySQL и PostgreSQL. ### B-Tree Основният инструмент на базите данни. Поддържа равенство (`=`), диапазони (`>`, `<`, `BETWEEN`) и сортиране (`ORDER BY`). B-Trees остават балансирани, което гарантира, че операциите за търсене, вмъкване и изтриване се изпълняват за време $O(\log n)$. ### Hash Хеш индексите съхраняват хеш на индексираната стойност и сочат към съответния ред. * **Postgres:** Поддържа явни хеш индекси. Те са изключително бързи ($O(1)$) за търсене по равенство, но не поддържат заявки за диапазон, сортиране или частично съвпадение на множество колони. * **MySQL (InnoDB):** Не поддържа явно създаване на хеш индекси. Вместо това използва **адаптивен хеш индекс (Adaptive Hash Index)** — вътрешна функция, при която InnoDB автоматично следи шаблоните на заявки върху B-Trees и изгражда хеш таблици в паметта за много чести търсения. ### GIN (Generalized Inverted Index) - Postgres GIN е предназначен за индексиране на съставни стойности, където трябва да търсите елементи *вътре* в стойността (като JSONB документи или масиви). GIN картографира отделните елементи в документа към техните физически TID на редовете. ```sql -- database/migrations/2026_05_31_postgres_features.sql -- Създаване на таблица с JSONB и GIN индекс в PostgreSQL CREATE TABLE user_profiles ( id BIGINT PRIMARY KEY, metadata JSONB NOT NULL ); CREATE INDEX idx_user_metadata_gin ON user_profiles USING GIN (metadata); -- Тази заявка използва GIN индекса за незабавно намиране на съвпадащи ключове SELECT * FROM user_profiles WHERE metadata @> '{"role": "administrator", "status": "active"}'; ``` ### Частични / Филтрирани индекси (Partial Indexes) Частичният индекс съдържа само подмножество от редовете в таблицата, дефинирано от `WHERE` условие. Това спестява огромно дисково пространство и поддържа индекса малък и бърз. * **Postgres:** Нативно поддържа частични индекси. * **MySQL:** Не поддържа частични индекси директно (към версия 8.0). Трябва да използвате функционални индекси с изрази, които се оценяват до `NULL`, за да постигнете подобен ефект, което е по-малко елегантно. ```sql -- database/migrations/2026_05_31_partial_index.sql -- Само за Postgres: Индексираме само активни неплатени поръчки за компактност CREATE INDEX idx_orders_active_unpaid ON orders (user_id) WHERE status = 'pending' AND amount > 100.00; ``` ### Индекси по израз / Функционални индекси Можете да индексирате резултата от функция или израз, вместо суровата стойност на колоната. Това е изключително полезно, когато заявките извършват манипулации върху колони в клаузата `WHERE`. ```sql -- database/migrations/2026_05_31_functional_index.sql -- Създаване на индекс по израз за оптимизиране на търсения без разлика в регистъра -- PostgreSQL: CREATE INDEX idx_orders_lower_status ON orders (LOWER(status)); -- MySQL 8.0+: CREATE INDEX idx_orders_lower_status ON orders ((LOWER(status))); ``` ### Покриващи индекси (Covering Indexes) Покриващият индекс е вторичен индекс, който съдържа всички колони, изисквани от дадена заявка. Това позволява на базата данни да изпълни заявката изцяло от страницата на индекса, без да докосва данните на таблицата (Heap или клъстерирания индекс). * В Postgres можете явно да прикачите колони с данни (които не са част от ключа) към индекс с помощта на клаузата `INCLUDE`. * В MySQL просто добавяте колоните към съставния индекс. ```sql -- database/migrations/2026_05_31_covering_index.sql -- Postgres: Индексът е сортиран по user_id, но съдържа и данните за amount/created_at CREATE INDEX idx_orders_covering ON orders (user_id) INCLUDE (amount, created_at); ``` --- ## 4. Излишно записване (Write Amplification) & цена за поддръжка Индексите не са безплатни. Всеки индекс, който добавяте към дадена таблица, забавя производителността при запис. Това се изразява като **излишно записване (Write Amplification)**. ### Разделяне на страници в B+Trees (Page Splits) Страниците на базата данни се разпределят със свободно пространство (fillfactor), за да се позволят бъдещи актуализации. Когато вмъквате ред, базата данни трябва да го запише в съответния B-Tree възел. Ако страницата на възела е пълна, възниква **разделяне на страница (Page Split)**: 1. Заделя се нова страница. 2. Приблизително 50% от ключовете от пълната страница се преместват в новата страница. 3. Родителската страница се актуализира с указател към новата страница. Тази операция изисква множество записи на диска и причинява фрагментация на индекса, което влошава производителността при последователно четене. ### Vacuuming срещу забавяне на изчистването (Purge Lag) Когато редовете се актуализират или изтриват, пространството, заето от старите записи, не може да бъде преизползвано веднага поради MVCC (Multi-Version Concurrency Control). * **Postgres (Autovacuum):** При UPDATE в Postgres се записва нов кортеж в купчината и индексите се актуализират да сочат към него. Това оставя \"мъртъв кортеж\" в страницата на купчината. Ако процесът autovacuum не може да смогне с почистването на тези мъртви кортежи, таблицата и нейните индекси се раздуват (bloat), което води до сериозно влошаване на производителността на паметта и диска. * **MySQL InnoDB (Purge Lag):** В InnoDB актуализациите се извършват на място в клъстерирания индекс, а старите версии се записват в сегмента за отмяна (Undo Log). Вторичните индекси обаче се променят, като старият запис се маркира като \"изтрит\" (delete-marked) и се вмъква новият запис. Фонова нишка, наречена **Purge Thread**, отговаря за премахването на тези маркирани за изтриване записи във вторичните индекси. Ако записите са твърде интензивни, забавянето на изчистването (**Purge Lag**) нараства, заемайки дисково пространство и причинявайки забавяне на заявките. --- ## 5. Чести грешки ### Грешка 1: Грешен ред на колоните в съставен индекс **Лоша практика:** Разработчикът очаква индексът да оптимизира заявките и по двете колони, но поставя колоната за диапазон първа. ```sql -- database/queries/bad_composite_order.sql -- Индексът е дефиниран като: (created_at, user_id) CREATE INDEX idx_bad_order ON orders (created_at, user_id); -- Заявка: SELECT * FROM orders WHERE created_at >= '2026-01-01 00:00:00' AND user_id = 42; ``` *Защо е лошо:* Филтърът за диапазон на `created_at` пречи на базата данни да използва частта `user_id` от индекса за точно намиране на редовете. Енджинът трябва да сканира индекса за всички записи след датата, проверявайки всеки един за съответния потребителски ID. **Добра практика:** ```sql -- database/queries/good_composite_order.sql -- Индексът е дефиниран като: (user_id, created_at) CREATE INDEX idx_good_order ON orders (user_id, created_at); -- Заявка: SELECT * FROM orders WHERE user_id = 42 AND created_at >= '2026-01-01 00:00:00'; ``` *Защо е добро:* Филтърът за точно равенство на `user_id` позволява на базата данни незабавно да скочи до записите на потребителя и след това да използва подредените листови възли на `created_at` за сканиране на диапазона. ### Грешка 2: Индексиране на колони с ниска кардиналност **Лоша практика:** Добавяне на индекс върху булева колона (напр. `is_active` или `has_paid`). ```sql -- database/queries/bad_low_cardinality.sql CREATE INDEX idx_orders_active ON orders (status); -- status има само стойности 'pending', 'completed' ``` *Защо е лошо:* Ако стойностите на статуса са равномерно разпределени, индексът няма да помогне. Оптимизаторът на заявки ще оцени цената на преминаването през вторичния индекс и след това извършването на случайни I/O търсения в клъстерирания индекс/купчината и ще реши, че последователното сканиране на таблицата е по-бързо. Индексът остава неизползван, но все пак забавя производителността при запис. --- ## 6. Тест за самопроверка Проверете разбирането си за архитектурите на индексите: ### Въпрос 1 Предположете, че имате съставен индекс `idx_test (A, B, C)` върху таблица. Коя от следните заявки **НЯМА** да може да използва индекса? 1. `WHERE A = 1 AND B = 2` 2. `WHERE B = 2 AND C = 3` 3. `WHERE A = 1 AND C = 3`
Кликнете тук, за да видите отговора **Отговор: Заявка 2 (`WHERE B = 2 AND C = 3`)** **Обяснение:** Съгласно правилото за най-левия префикс, заявката трябва да филтрира по първата колона от индекса (`A`), за да го използва. Тъй като Заявка 2 не филтрира по `A`, базата данни не може да премине през коренните възли на B-Tree и трябва да извърши пълно сканиране на таблицата. Заявка 3 *може* да използва индекса, но само частта `A`; тя ще локализира записите, където `A = 1`, и след това ще ги филтрира ръчно за `C = 3`.
--- ### Въпрос 2 Защо актуализирането на неиндексирана колона в PostgreSQL понякога предизвиква излишно записване в индексите (index write amplification), докато в MySQL InnoDB това не се случва?
Кликнете тук, за да видите отговора **Отговор:** Поради разликата между структурите тип Купчина (Heap) и Клъстериран индекс. * В PostgreSQL, ако UPDATE не може да изпълни HOT (Heap Only Tuples) оптимизация (например ако няма място на страницата), нова версия на реда се записва на различна страница. Това променя физическия адрес (TID) на реда. В резултат на това *всички* индекси на тази таблица трябва да бъдат актуализирани, за да сочат към новия TID, което причинява излишно записване в индексите. * В MySQL InnoDB редът остава в същия листов възел на клъстерирания индекс (освен ако самият първичен ключ не бъде актуализиран). Вторичните индекси сочат към стойността на първичния ключ, а не към физически адрес на диска, което означава, че техните листови възли не се нуждаят от актуализация.
--- ### Въпрос 3 Имате таблица с 10 милиона реда. Изпълнявате следната заявка: `SELECT user_id, status FROM orders WHERE user_id = 100500;` Индексът на `user_id` е дефиниран като: `CREATE INDEX idx_user ON orders (user_id);` Как можете да оптимизирате тази заявка, за да предотвратите търсене в страниците с данни на таблицата?
Кликнете тук, за да видите отговора **Отговор:** Създайте **покриващ индекс (covering index)**, който включва `status`. * В PostgreSQL: `CREATE INDEX idx_user_status ON orders (user_id) INCLUDE (status);` * В MySQL (или PostgreSQL): `CREATE INDEX idx_user_status ON orders (user_id, status);` **Обяснение:** Чрез добавяне на `status` към индекса, всички колони, изисквани в `SELECT` и `WHERE` клаузите, се съдържат изцяло в страницата на индекса. Енджинът на базата данни може да извърши **Index Only Scan**, като заобиколи напълно търсенето в купчината или клъстерирания индекс.