Дерева. Пошук. Алгоритми. Бази даних

Це відео є підготовчим до більш глибокого занурення в бази даних.
Спробував відповісти на наступні питання:
✅Що таке індекс в базі даних?
✅Чим відрізняються різні типи дерев?
✅Чому пошук по 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 #алгоритми

[@AboutProgramming]

Вже всі підготовчі відео для головного виклав. В наступний раз має бути круте продовження 😎

[@nztzn]

Дуже крутий україномовний контент. Успіхів у розвитку!

[@AboutProgramming]

Дякую! 🙂

[@malds.0629]

Дуже круте відео! Дякую за україномовниий контент!

[@AdminAdmin-sl2qf]

❤❤❤❤❤❤❤❤❤❤❤

[@BorysPratsiuk]

Окреме дякую за україномовний контент!!!

[@v.ilchenko]

Аж ностальгія пробрала. Згадав як ми вчились балансувати ці дерева після роботи 🤓

[@lilysea688]

Дякую! Дуже корисно і дуже зрозуміле пояснення👌

[@sstage44]

Крутий контент! Дуже цікаво слухати. Особливо знаючи величезний досвід автора)

[@artemtrush]

Супер ✨

[@kyivarcan]

Дуже дякую за інформацію, зрозуміла та наглядна подача, будь-ласка, продовжуй далі, по базам данних такого контенту дуже мало (особливо україномовного)

[@bohdanartiukhov7238]

спасибо за то что ты делаешь :)

[@pavel7930]

Круто! Дякую!

[@Ya_Kor]

Мій випадковий вибір, з чого почати знайомство з каналом виявився не випадковим) На лекції по структурах даних якраз освітили все, крім B-Tree. Дякую за чудове та лаконічне пояснення. Пішов досліджувати решту контенту)

[@user-ux8yp3si4d]

Дуже корисно, нещодавно сам намагався розібратися с BRT, чекаю нові відео 🦾

[@user-kn4hv3bg6g]

Дякую! Круто!

[@dmytrofiialo4818]

Дякую за відео

[@oksanakhortytsia]

Дякую! Дуже корисно і по справі!

[@atsybulsky]

Толковий відос, дякую :) Коротко та ясно.

[@user-pt7nz6vc7s]

Дякую за відео 😊

[@user-si4sv1sv9b]

Дякую

[@vladyslavsosnov8412]

Дякую за цікавий контент

[@sviat_d]

Круто. Інформативно, зрозуміло і лаконічно 👍

[@andriyleliv4608]

Дуже кльово - дякую!

[@rickbacker1]

Дуже круте відео, стало ясніше як цей індекс працює в середині! Дякую Вам!

[@user-gywunrl]

дуже крутий контент, дякую

[@andriishymkiv6364]

лайк не дивлячись)

[@oleksiiderkach4840]

Дякую за відео!

[@TheKidomaz]

Дуже круто і головне зрозуміло, підписався)

[@BG-cg2op]

Awesome!

[@PonomarenkoO]

Дякую!

[@oleksandrsecondname]

З мене лайк дивлячись) дуже струтуровано освіжає знання

[@Philip_Just]

чекаю на наступне відео)

[@MyHor]

Круто, дуже круто.

[@ivanovserg8795]

Дуже цікаво! Дякую!

[@RomanTsyupryk]

Велике дякую вам за це відео.

[@mshkotnyar]

Просто топовий канал. Частину знав, частина для мене нове. Дуже круто, дуже

[@romanyukartem757]

Все доволі доступно, супер, дякую. Цікавим б також було б відео із додаванням індекса на високо-навантажену (на запис) та велику таблицю в базі данихю

[@Roman-oi9el]

Готовий до наступного відео :)

[@denyspapushaiev5604]

топовий український контент. щиро дякую!

[@romkalily]

Але то красава!!!!! Самий крутий український контент який я зараз дивлюсь!!

[@yeoh4001]

Гарний контент, видно що хотів розповісти про все і одразу, а по факту стрибав з теми на тему і нічого детально не розповів. Можливо краще було б зробити окремі відео по кожному з дерев, оцінити worst/best complexity, в кінці реалізацію на тій же Node js?

[@AboutProgramming]

Дякую за відгук! Ідея була зробити одне відео про індекси а базах, але в результаті розбив на декілька 🙂 розбивати ще далі можна було, але тоді не буде порівняльного огляду в одному відео. Відносно реалізації, то це вже не так цікаво, оскільки багато таких відео є й властивості дерев в першу чергу залежать від їх структури, а реалізація того самого b дерева буде складною й великою. Більш цікаво написати код, який показує ефект від використання дерев. В планах є зробити окремі відео під quad tree або binary heap. Там є класні юз-кейси

[@victorshnaider7305]

Коли писав червоно-чорне дерево в академії то над видаленям ноди думав цілий день😅

[@rostik18]

Прості речі, а вже й забулося (за B+ tree навіть не знав) Дякую Автору! цікаво, в NoSQL такий самий принцип?

[@AboutProgramming]

Так. Більшість баз використовувує B+tree для індексів (mongodb, наприклад, теж)

[@rayetzki]

Як варіант, було б цікаво ще в деталях про partitioning послухати

[@user-eb9iv8gx7e]

Дякую за відео. Трішки не вірно про AVL дерева: їх використання поширене у документоорієнтованих базах даних

[@AboutProgramming]

А які саме бази даних використовують AVL дерева для індексування? Бази, що знаю, типу MongoDB, CouchDB, DynamoDB використовують B-Tree для індексів.

[@artemzabolotnyi3838]

База

[@AboutProgramming]

Так. База, яку варто знати всім, хто працює з базами :) Але й в цьому відео є не зовсім очевидні речі. Наприклад, багато хто не знає, що fanout factor залежить від розміру наших даних (з колонок, які потрапляють в індекс), а не просто константа. Й відповідно page size може на ци впливати (й на максимальний розмір рядка)

[@552456829]

Привіт. Чи використовуюєте ви планшет для нотатків за допомогою стилуса? Якщо так, то я який мобільний додаток? Дякую.

[@AboutProgramming]

У мене Galaxy Tab S7 FE й часто просто помалювати його користую. Програма для нотаток там вбудована - Samsung Notes

[@shchekavytsia]

Дякую за відео!!!! Цікаво, а як працює like пошук індексованих даних з джоінами на не індексовані

[@AboutProgramming]

В цілому за визначення того, як обробляти запит й які використовувати індекси відповідає query planner. Він аналізує різні варіанти виконання й обирає той, який набирає найбільший бал. Але при великій кількості джойнів й таблиць може бути таке, що перебрати варіанти занадто дорого, тоді база може навіть просто прорахувати певну кількість рандомних варіантів й обрати вже з них. Також часом query planner часом пробує альтернативні плани, щоб перевірити як вони працюють (у нас були від цього проблеми й доводилося писати хінти в запитах, щоб база використовувала правильні індекси завжди). Ну й звісно в різних базах query planner працює по різному. Що він обере залежить від того скільки даних, від селективності індексу, від кардинальності даних й тд. Тут самому треба закопуватися :) Але можливо має сенс відео про те, як це все перевіряти й як шукати проблемні місця в запитах

[@shchekavytsia]

@@AboutProgramming дякую за відповідь і круті відео!👍👍👍 треба почати і собі програмувати щось.

[@itsimplified]

Для тих, хто не в темі, варто уточнювати, що під записом log мається на увазі логарифм із основою 2.

[@AboutProgramming]

Насправді різниці немає. Так більшість алгоритмів має базу 2, але щоб сконвертувати одну базу в іншу нам треба просто помножити на константу, яка не залежить від n. Тобто це як O(n) й O(10*n) це одне й те саме, оскільки множення "10" не впливає на характер залежності. Це називають hidden constant. Тобто при збільшенні n в 2 рази час виконання збільшиться в 2 рази, а чи то зміна від 10 до 20 чи від 100 до 200 нам без різниці. Аналогічно й з базою логарифма

[@itsimplified]

@@AboutProgramming Але це впливає на розуміння, чому саме логарифм при діленні навпіл.

[@nanvlad]

@@itsimplified це коли ми користуємося правилом золотого перетину, а якщо кожен рівень поділити на 3 значення, то буде log 3n, на 4 - log4n і т.д., тому в узагальненому записі вказують просто logn

[@dbvech]

Комент у підтримку. Цікавий контент!

[@avazart614]

Але не зрозуміло навіщо вик. дерева з лог.склад. коли є хеш таблиці з конст. складністю?

[@AboutProgramming]

Хеш таблиці дуже крута структура даних й окрім того дійсно існують хеш-індекси в mysql/postgres, але дані там будуть не відсортовані. Тобто це просто key-value storage. В результаті : 1. Не можемо робити запити виду "price > 100", а тільки пошук на конкретне значення. Й не можемо зробити скан. 2. Не можна робити пошук типу "name like 'apple%'" 3. Не можемо використовувати сортування. Тобто, кожен раз, коли в UI хтось сортує дані по певний колонці, то база не може використовувати індекси. Тобто, це перетворює MySQL умовно в Redis

[@avazart614]

@@AboutProgramming Зрозуміло, дякую.

[@bohdanmarynushkin7630]

а, ні. може

[@markh3329]

шось нагнітаєш важкість про просте. аж 15 хвилин.

[@AboutProgramming]

Важке ж можеш пропускати

[@markh3329]

дурна музика

[@AboutProgramming]

Якщо є кращі варіанти з бібліотекі ютуб, то готовий розглянути

[@dimashtef7077]

мабуть найзрозуміліше пояснення "дерев", ще й українською

[@user-zc3vz2eg3s]

було б круто почути по криптографії огляд (хороші і погані практики) @AboutOrogramming

[@AdminAdmin-sl2qf]

❤❤❤❤❤❤❤❤❤❤❤❤