Дерева. Пошук. Алгоритми. Бази даних
Вставка
- Опубліковано 22 чер 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 #алгоритми
Вже всі підготовчі відео для головного виклав. В наступний раз має бути круте продовження 😎
Окреме дякую за україномовний контент!!!
Дуже круте відео! Дякую за україномовниий контент!
Дуже крутий україномовний контент. Успіхів у розвитку!
Дякую! 🙂
Дякую за відео!
Аж ностальгія пробрала. Згадав як ми вчились балансувати ці дерева після роботи 🤓
Дуже круте відео, стало ясніше як цей індекс працює в середині!
Дякую Вам!
Дуже корисно, нещодавно сам намагався розібратися с BRT, чекаю нові відео 🦾
Дякую
Мій випадковий вибір, з чого почати знайомство з каналом виявився не випадковим)
На лекції по структурах даних якраз освітили все, крім B-Tree.
Дякую за чудове та лаконічне пояснення.
Пішов досліджувати решту контенту)
Дякую! Дуже корисно і дуже зрозуміле пояснення👌
Крутий контент! Дуже цікаво слухати. Особливо знаючи величезний досвід автора)
Але то красава!!!!!
Самий крутий український контент який я зараз дивлюсь!!
Толковий відос, дякую :) Коротко та ясно.
Круто, дуже круто.
Дуже дякую за інформацію, зрозуміла та наглядна подача, будь-ласка, продовжуй далі, по базам данних такого контенту дуже мало (особливо україномовного)
Просто топовий канал. Частину знав, частина для мене нове. Дуже круто, дуже
топовий український контент. щиро дякую!
Дякую! Дуже корисно і по справі!
Готовий до наступного відео :)
Дуже круто і головне зрозуміло, підписався)
Круто. Інформативно, зрозуміло і лаконічно 👍
Велике дякую вам за це відео.
❤❤❤❤❤❤❤❤❤❤❤
З мене лайк дивлячись) дуже струтуровано освіжає знання
Дуже кльово - дякую!
дуже крутий контент, дякую
Все доволі доступно, супер, дякую.
Цікавим б також було б відео із додаванням індекса на високо-навантажену (на запис) та велику таблицю в базі данихю
лайк не дивлячись)
Дуже цікаво! Дякую!
Дякую за відео 😊
Дякую за цікавий контент
Дякую! Круто!
Супер ✨
Круто! Дякую!
Дякую за відео
Дякую!
спасибо за то что ты делаешь :)
чекаю на наступне відео)
Гарний контент, видно що хотів розповісти про все і одразу, а по факту стрибав з теми на тему і нічого детально не розповів. Можливо краще було б зробити окремі відео по кожному з дерев, оцінити worst/best complexity, в кінці реалізацію на тій же Node js?
Дякую за відгук! Ідея була зробити одне відео про індекси а базах, але в результаті розбив на декілька 🙂 розбивати ще далі можна було, але тоді не буде порівняльного огляду в одному відео. Відносно реалізації, то це вже не так цікаво, оскільки багато таких відео є й властивості дерев в першу чергу залежать від їх структури, а реалізація того самого b дерева буде складною й великою. Більш цікаво написати код, який показує ефект від використання дерев. В планах є зробити окремі відео під quad tree або binary heap. Там є класні юз-кейси
Прості речі, а вже й забулося (за B+ tree навіть не знав)
Дякую Автору!
цікаво, в NoSQL такий самий принцип?
Так. Більшість баз використовувує B+tree для індексів (mongodb, наприклад, теж)
Awesome!
Дякую за відео. Трішки не вірно про AVL дерева: їх використання поширене у документоорієнтованих базах даних
А які саме бази даних використовують AVL дерева для індексування? Бази, що знаю, типу MongoDB, CouchDB, DynamoDB використовують B-Tree для індексів.
Як варіант, було б цікаво ще в деталях про partitioning послухати
База
Так. База, яку варто знати всім, хто працює з базами :) Але й в цьому відео є не зовсім очевидні речі. Наприклад, багато хто не знає, що fanout factor залежить від розміру наших даних (з колонок, які потрапляють в індекс), а не просто константа. Й відповідно page size може на ци впливати (й на максимальний розмір рядка)
Дякую за відео!!!! Цікаво, а як працює 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
Привіт. Чи використовуюєте ви планшет для нотатків за допомогою стилуса? Якщо так, то я який мобільний додаток? Дякую.
У мене Galaxy Tab S7 FE й часто просто помалювати його користую. Програма для нотаток там вбудована - Samsung Notes
Комент у підтримку. Цікавий контент!
Але не зрозуміло навіщо вик. дерева з лог.склад. коли є хеш таблиці з конст. складністю?
Хеш таблиці дуже крута структура даних й окрім того дійсно існують хеш-індекси в mysql/postgres, але дані там будуть не відсортовані. Тобто це просто key-value storage. В результаті :
1. Не можемо робити запити виду "price > 100", а тільки пошук на конкретне значення. Й не можемо зробити скан.
2. Не можна робити пошук типу "name like 'apple%'"
3. Не можемо використовувати сортування. Тобто, кожен раз, коли в UI хтось сортує дані по певний колонці, то база не може використовувати індекси.
Тобто, це перетворює MySQL умовно в Redis
@@AboutProgramming Зрозуміло, дякую.
а, ні. може
шось нагнітаєш важкість про просте. аж 15 хвилин.
Важке ж можеш пропускати
дурна музика
Якщо є кращі варіанти з бібліотекі ютуб, то готовий розглянути
мабуть найзрозуміліше пояснення "дерев", ще й українською
було б круто почути по криптографії огляд (хороші і погані практики) @AboutOrogramming
❤❤❤❤❤❤❤❤❤❤❤❤