▶ Віктор Турський про програмування / навігатор

треки / 03

Бази даних і структури даних

9 відео · 5 год 5 хв

Найщільніший і найретельніше вибудуваний кластер каналу. Віктор будує навчальний шлях, де кожне відео створює проблему, яку розвʼязує наступне: спершу сирий шок від навіщо взагалі індекси (той самий запит, у 60 000 разів швидше), потім дерева, щоб пояснити, чим індекс є фізично і чому диски вимагають неглибоких B+ дерев, далі нутрощі індексів (MySQL проти Postgres, кластерний проти heap, UUID проти автоінкременту — з експериментами на 16 млн рядків), потім місце, де B-дерева пасують, — пошук усередині рядка — яке відкриває повнотекстовий пошук та інвертовані індекси (побудовані вручну, стиснені й забенчмарчені проти рідного FULLTEXT у MySQL), і нарешті фільтри Блума як імовірнісний фінал, що обганяє кожну базу даних і кеш у цій драбині. Усе вимірюється наживо, все спирається на його історії з практики — насамперед на систему повнотекстового пошуку на 300 ТБ, яку він власноруч побудував у продакшені, — а повторюваний висновок і є тезою каналу: знай властивості й нутрощі своїх інструментів, а не хайп.

Порядок перегляду

  1. 1
    Навіщо потрібні індекси в базі даних — розберемо на прикладі середній

    жива демонстрація в MySQL: 3.3 с → 0.05 мс на 10 млн рядків, плюс де індекси ламаються

    Індекси баз данихАлгоритмічна складністьB-tree / B+ treeПовнотекстовий пошукІнвертований індексMySQL
    19:22 · 15 розділів
  2. 2
    Чому алгоритми важливі — розберемо на прикладі середній

    O(n*m) проти O(n+m), закодоване наживо на JS і спроєктоване на індекси баз даних

    Алгоритмічна складністьСтруктури данихХешуванняІндекси баз данихB-tree / B+ tree
    23:44 · 15 розділів
  3. 3
    Дерева. Пошук. Алгоритми. Бази даних середній

    місток на дошці: бінарний пошук → BST → AVL → неглибокі дискові B+ дерева

    B-tree / B+ treeСтруктури данихАлгоритмічна складністьІндекси баз данихMySQLPostgreSQL
    15:56 · 13 розділів
  4. 4
    Як працюють індекси в базах на прикладі: MySQL vs Postgres, UUID vs Auto Increment просунутий

    хардкорні нутрощі з експериментами на 16 млн рядків: кластерний проти heap, MVCC, штрафи за UUID

    Індекси баз данихB-tree / B+ treeMVCC (багатоверсійне керування конкурентним доступом)UUID проти auto-increment у первинних ключахАлгоритмічна складністьГлибоке вивчення фундаментальних речей
    37:42 · 15 розділів
  5. 5
    Як працює повнотекстовий пошук: будуємо інвертований індекс на практиці просунутий

    вручну будує інвертований індекс продакшен-рівня через map-reduce; бʼє MySQL LIKE: 40 с → 21 мс

    Повнотекстовий пошукІнвертований індексСтиснення індексуMap-reduceBase64Індекси баз даних
    48:15 · 15 розділів
  6. 6
    Як працює повнотекстовий пошук, частина 2: запитання-відповіді й подальші оптимізації просунутий

    розділення на файл токенів + бінарні postings, n-грамні токенізатори, пошук через S3 Range-запити

    Повнотекстовий пошукІнвертований індексСтиснення індексуBase64UUID проти auto-increment у первинних ключахElasticsearch
    14:34 · 8 розділів
  7. 7
    Геніальна структура даних й як її покращив Firefox середній

    фільтри Блума проти Map/MySQL/Redis/Memcached на 10 млн ключів, і каскад CRLite у Firefox

    Фільтр БлумаСтруктури данихХешуванняHTTPS і TLSІндекси баз данихАлгоритмічна складність
    51:02 · 15 розділів
  8. 8
    Питання та відповіді №1: чи захистить HTTPS? середній

    Q&A-продовження про UUID-ключі та стиснення інвертованого індексу

    HTTPS і TLSDHCP (Dynamic Host Configuration Protocol)DNS (Domain Name System)NAT і основи мережПрактики безпекиСоціальна інженерія
    17:50 · 15 розділів
  9. 9
    Відповідаю на питання №2 середній

    алгоритми в реальному житті: аналіз складності на ревʼю, історія з практики про топологічне сортування стека

    Карʼєра і зростанняШІ-агенти для кодуванняАлгоритмічна складністьСтруктури данихПроєктування програмного забезпеченняАбстракції
    1:16:50 · 25 розділів