Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що означає "B-tree структура індексу"?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)B-tree - базовий тип структури індексу в СУБД, який дозволяє виконувати пошук, вставку й видалення за логарифмічний час O(log n): зберігає ключі у відсортованому вигляді в самобалансованому дереві (зазвичай 2-4 рівні навіть при мільйонах рядків) і дає змогу швидко знаходити потрібний діапазон значень. **Ключове:** B-tree ідеальний для `WHERE column = X`, діапазонів, `ORDER BY` і `JOIN` за індексованими ключами, але погано підходить для `LIKE '%text'` із символом підстановки на початку - там потрібні інші типи індексів (GIN, GiST, FTS).Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)ЗображенняB-tree - це базовий тип структури індексу в СУБД, який дозволяє виконувати пошук, вставку й видалення за **логарифмічний час O(log n)**. Він використовується в PostgreSQL, MySQL (InnoDB), Oracle та ін. Його завдання - зберігати ключі у відсортованому вигляді й давати змогу швидко знаходити потрібний діапазон значень. Якщо по суті, без води, на рівні middle: ### 1. Що таке B-tree в контексті індексу Це **збалансоване деревоподібне сховище**, в якому: - кожен вузол містить **відсортовані ключі** - вузли мають **посилання на дочірні вузли** - дерево **завжди збалансоване за висотою** (зазвичай 2-4 рівні навіть при мільйонах рядків) - листки містять посилання на фізичні рядки таблиці (або самі дані - залежить від реалізації) ### 2. Як B-tree пришвидшує пошук Алгоритм пошуку працює як у телефонному довіднику: - БД іде від кореня - за ключами всередині вузла розуміє, у якого "нащадка" потрібно спуститися - повторює крок, поки не дійде до листка - отримує адресу рядка, не перебираючи всю таблицю Замість `N` порівнянь - **~log₂(N)**. На великих обсягах різниця величезна: замість 1 000 000 порівнянь - близько 20. ### 3. Чому саме B-tree, а не звичайне бінарне дерево Тому що звичайне дерево пошуку легко "складається" в лінію й деградує до O(n). B-tree **жорстко контролює баланс**, тому ефективність стабільна й передбачувана. ### 4. Для яких запитів B-tree ідеальний - `WHERE column = X` - діапазони: `BETWEEN`, `>`, `<` - `ORDER BY`, якщо порядок збігається з індексом - `JOIN` за індексованими ключами ### 5. Важливий нюанс B-tree **погано підходить** для `LIKE '%text'` (символ підстановки на початку), тому що такий запит не можна шукати за сортуванням - там потрібен повний перебір чи інші типи індексів (GIN, GiST, FTS). ### Підсумок B-tree - це самобалансована індексна структура, яка зберігає відсортовані ключі й дозволяє шукати значення за O(log n), тому запити за умовою, діапазоном, сортуванням і join'ами працюють швидко незалежно від розміру таблиці. Якщо потрібно - можу в наступному повідомленні намалювати B-tree на прикладі реального індексу й покроково показати, як відбувається `WHERE value = 42` на рівні вузлів.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.