Дерева. Пошук. Алгоритми. Бази даних
HTML-код
- Опубликовано: 6 июн 2024
- Це відео є підготовчим до більш глибокого занурення в бази даних.
Спробував відповісти на наступні питання:
✅Що таке індекс в базі даних?
✅Чим відрізняються різні типи дерев?
✅Чому пошук по BST може бути повільним?
✅Чому бази даних не використовують бінарний пошук?
✅B-дерево проти B+ дерева
✅Індекси Postgres, MySQL
Станьте спонсором цього каналу: / @aboutprogramming
Допоможіть каналу розвиватися й отримуйте доступ до ексклюзивного контенту.
Зміст відео:
0:00 - Вступ
0:42 - Що таке індекси?
4:00 - Бінарне дерево
6:10 - Чому може бути O(n)?
7:05 - Збалансоване дерево
7:38 - AVL Tree та RB Tree
8:51 - B-Tree проти BST
12:27 - B+ Tree
14:35 - Анонс контенту
🏠 Мої соцмережі:
Жабаскрипт в телеграмі - t.me/jabascript
Я в Твітер - / viktorturskyi
Мій Linkedin - / turskyi
#програмування #українською #programming #javascript #database #mysql #алгоритми
Вже всі підготовчі відео для головного виклав. В наступний раз має бути круте продовження 😎
Мій випадковий вибір, з чого почати знайомство з каналом виявився не випадковим)
На лекції по структурах даних якраз освітили все, крім B-Tree.
Дякую за чудове та лаконічне пояснення.
Пішов досліджувати решту контенту)
Окреме дякую за україномовний контент!!!
❤❤❤❤❤❤❤❤❤❤❤
Аж ностальгія пробрала. Згадав як ми вчились балансувати ці дерева після роботи 🤓
Дякую
Дуже круте відео! Дякую за україномовниий контент!
Дуже круте відео, стало ясніше як цей індекс працює в середині!
Дякую Вам!
Дякую за відео!
Дуже корисно, нещодавно сам намагався розібратися с BRT, чекаю нові відео 🦾
Дуже дякую за інформацію, зрозуміла та наглядна подача, будь-ласка, продовжуй далі, по базам данних такого контенту дуже мало (особливо україномовного)
Крутий контент! Дуже цікаво слухати. Особливо знаючи величезний досвід автора)
Готовий до наступного відео :)
Дякую! Дуже корисно і дуже зрозуміле пояснення👌
Круто, дуже круто.
Просто топовий канал. Частину знав, частина для мене нове. Дуже круто, дуже
Дуже крутий україномовний контент. Успіхів у розвитку!
Дякую! 🙂
Все доволі доступно, супер, дякую.
Цікавим б також було б відео із додаванням індекса на високо-навантажену (на запис) та велику таблицю в базі данихю
Дякую! Дуже корисно і по справі!
топовий український контент. щиро дякую!
Толковий відос, дякую :) Коротко та ясно.
Але то красава!!!!!
Самий крутий український контент який я зараз дивлюсь!!
лайк не дивлячись)
Круто! Дякую!
Велике дякую вам за це відео.
Дуже круто і головне зрозуміло, підписався)
Супер ✨
Awesome!
Дякую за відео
Дуже кльово - дякую!
спасибо за то что ты делаешь :)
Дякую! Круто!
дуже крутий контент, дякую
Круто. Інформативно, зрозуміло і лаконічно 👍
Дякую за цікавий контент
Дякую за відео 😊
З мене лайк дивлячись) дуже струтуровано освіжає знання
Дякую!
чекаю на наступне відео)
Дуже цікаво! Дякую!
Гарний контент, видно що хотів розповісти про все і одразу, а по факту стрибав з теми на тему і нічого детально не розповів. Можливо краще було б зробити окремі відео по кожному з дерев, оцінити worst/best complexity, в кінці реалізацію на тій же Node js?
Дякую за відгук! Ідея була зробити одне відео про індекси а базах, але в результаті розбив на декілька 🙂 розбивати ще далі можна було, але тоді не буде порівняльного огляду в одному відео. Відносно реалізації, то це вже не так цікаво, оскільки багато таких відео є й властивості дерев в першу чергу залежать від їх структури, а реалізація того самого b дерева буде складною й великою. Більш цікаво написати код, який показує ефект від використання дерев. В планах є зробити окремі відео під quad tree або binary heap. Там є класні юз-кейси
Прості речі, а вже й забулося (за B+ tree навіть не знав)
Дякую Автору!
цікаво, в NoSQL такий самий принцип?
Так. Більшість баз використовувує B+tree для індексів (mongodb, наприклад, теж)
Дякую за відео. Трішки не вірно про AVL дерева: їх використання поширене у документоорієнтованих базах даних
А які саме бази даних використовують AVL дерева для індексування? Бази, що знаю, типу MongoDB, CouchDB, DynamoDB використовують B-Tree для індексів.
Як варіант, було б цікаво ще в деталях про partitioning послухати
Привіт. Чи використовуюєте ви планшет для нотатків за допомогою стилуса? Якщо так, то я який мобільний додаток? Дякую.
У мене Galaxy Tab S7 FE й часто просто помалювати його користую. Програма для нотаток там вбудована - Samsung Notes
Дякую за відео!!!! Цікаво, а як працює like пошук індексованих даних з джоінами на не індексовані
В цілому за визначення того, як обробляти запит й які використовувати індекси відповідає query planner. Він аналізує різні варіанти виконання й обирає той, який набирає найбільший бал. Але при великій кількості джойнів й таблиць може бути таке, що перебрати варіанти занадто дорого, тоді база може навіть просто прорахувати певну кількість рандомних варіантів й обрати вже з них. Також часом query planner часом пробує альтернативні плани, щоб перевірити як вони працюють (у нас були від цього проблеми й доводилося писати хінти в запитах, щоб база використовувала правильні індекси завжди). Ну й звісно в різних базах query planner працює по різному. Що він обере залежить від того скільки даних, від селективності індексу, від кардинальності даних й тд. Тут самому треба закопуватися :) Але можливо має сенс відео про те, як це все перевіряти й як шукати проблемні місця в запитах
@@AboutProgramming дякую за відповідь і круті відео!👍👍👍 треба почати і собі програмувати щось.
Для тих, хто не в темі, варто уточнювати, що під записом log мається на увазі логарифм із основою 2.
Насправді різниці немає. Так більшість алгоритмів має базу 2, але щоб сконвертувати одну базу в іншу нам треба просто помножити на константу, яка не залежить від n. Тобто це як O(n) й O(10*n) це одне й те саме, оскільки множення "10" не впливає на характер залежності. Це називають hidden constant. Тобто при збільшенні n в 2 рази час виконання збільшиться в 2 рази, а чи то зміна від 10 до 20 чи від 100 до 200 нам без різниці. Аналогічно й з базою логарифма
@@AboutProgramming Але це впливає на розуміння, чому саме логарифм при діленні навпіл.
@@itsimplified це коли ми користуємося правилом золотого перетину, а якщо кожен рівень поділити на 3 значення, то буде log 3n, на 4 - log4n і т.д., тому в узагальненому записі вказують просто logn
База
Так. База, яку варто знати всім, хто працює з базами :) Але й в цьому відео є не зовсім очевидні речі. Наприклад, багато хто не знає, що fanout factor залежить від розміру наших даних (з колонок, які потрапляють в індекс), а не просто константа. Й відповідно page size може на ци впливати (й на максимальний розмір рядка)
Комент у підтримку. Цікавий контент!
Але не зрозуміло навіщо вик. дерева з лог.склад. коли є хеш таблиці з конст. складністю?
Хеш таблиці дуже крута структура даних й окрім того дійсно існують хеш-індекси в mysql/postgres, але дані там будуть не відсортовані. Тобто це просто key-value storage. В результаті :
1. Не можемо робити запити виду "price > 100", а тільки пошук на конкретне значення. Й не можемо зробити скан.
2. Не можна робити пошук типу "name like 'apple%'"
3. Не можемо використовувати сортування. Тобто, кожен раз, коли в UI хтось сортує дані по певний колонці, то база не може використовувати індекси.
Тобто, це перетворює MySQL умовно в Redis
@@AboutProgramming Зрозуміло, дякую.
а, ні. може
шось нагнітаєш важкість про просте. аж 15 хвилин.
Важке ж можеш пропускати
мабуть найзрозуміліше пояснення "дерев", ще й українською
дурна музика
Якщо є кращі варіанти з бібліотекі ютуб, то готовий розглянути
було б круто почути по криптографії огляд (хороші і погані практики) @AboutOrogramming
❤❤❤❤❤❤❤❤❤❤❤❤