🦒
System Analyst | Knowledge base
  • Введение
  • Soft skills
    • 📍Продукт
      • Роли в IT продукте
        • Системный аналитик (SA)
        • Бизнес-аналитик (BA)
        • SA vs BA
        • 📎Другие аналитики
      • Жизненный цикл продукта
      • Методологии разработки
        • Waterfall
        • Agile
          • Scrum
          • Kanban
      • 📎Целеполагание
        • SMART
        • Матрица Эйзенхауэра
        • RICE
        • 🔒HADI
    • 📍Требования
      • Классификация требований
        • Уровень: Бизнес
        • Уровень: Пользователь
          • Use case
          • User story
          • 📎Job story
        • Уровень: Продукт
          • Функциональные требования
          • Нефункциональные требования
      • Качества требований
      • Методы сбора требований
      • Техническое задание (ТЗ)
  • Hard skills
    • 📍Базы данных
      • Реляционные
        • Транзакции
          • 🔒CAP
        • Нормальные формы
        • SQL
          • DML
          • DDL/DCL/TCL
          • 📎Представления VIEW
        • Констрейты
        • 📎Типы данных
        • 🔒Middle+
          • Особенности работы с конкертными реляционными БД
      • Нереляционные
        • Примеры использования
        • 🔒Middle+
          • Колоночные
            • Сlickhouse
          • Ключ-значение
          • Матричные
          • Документо-ориентированные
          • Графовые
            • JanusGraph | Neo4j etc
      • Масштабирование БД
      • Оптимизация БД
        • 📎Типы индексов
        • 📎Уникальные индексы
        • 🔒Анатомия плана запроса
      • 📎Какую СУБД выбрать
      • 📎Хранение и анализ данных
        • ETL
        • DWH
          • DWH vs Data Lake vs Data Mart
        • OLAP
          • OLAP vs OLTP
        • BI-аналитика
    • 📍Интеграции
      • Форматы данных
        • JSON + JSON Schema
          • 🔒AVRO
        • JSON vs XML
      • Виды интеграций
        • Синхронное взаимодействие
          • REST
            • RESTful принципы
              • Отсутствие состояния (Авторизация)
                • 🔒OAuth / OpenID Connect
              • Кеширование
              • Единообразие интерфейса (CRUD)
                • Запрос/ответ
              • 🔒Cтепень зрелости REST API
            • Проектирование API
            • 📎Асинхронный REST
          • SOAP
            • XSD
            • WSDL
          • REST vs SOAP
        • Асинхронное взаимодействие
          • Kafka
          • RabbitMQ
          • Kafka vs RabbitMQ
          • ESB
          • gRPC
            • Правила proto-контракта
            • Protobuf vs JSON
            • Сравнительная таблица
          • Другое
          • 🔒WebSocket API
        • Sync vs Async
      • 🔒Middle+
        • Stateful vs Stateless
        • Apache Flink
        • оркестрация и хореография
    • 📍Проектирование
      • Архитектура
        • Монолит
        • Микросервисы
          • Паттерны реализации
        • Монолит vs Микросервисы
        • 🔒Middle+
          • Бессерверная
          • Сервис-ориентированная (SOA)
          • Другое
      • Нотации и диаграммы
        • UML
          • Диаграмма классов
          • Диаграмма последовательности
            • Фреймы
          • Диаграмма прецедентов (use case)
          • 🔒Middle+
            • Диаграмма деятельности/активности
            • Диаграмма состояний
        • BPMN
          • Основные элементы
        • BPMN vs UML
        • ERD
        • 📎IDEF0
      • Прототипирование
        • Figma vs Axure
      • Мониторинг
        • Логирование
        • Метрики
        • Алерты
        • 🔒Инструменты
          • Grafana
          • Prometheus
          • ELK
            • Elasticsearch
            • Logstash
            • Kibana
      • 🔐Системный дизайн
    • 📎DevOps for SA
      • Основы сетей
        • OSI
        • TCP/IP
        • HTTP
        • DNS
      • Git (VCS)
        • GitHub vs GitLab
      • Развертывание приложений
        • CI/CD
        • 🔒Middle+
          • Виртуализация/контеризация
            • ✍️Docker
            • Kubernetes
              • ✍️Openshift
      • Cloud Native
        • Сервисы облачных вычислений
        • Cloud-native app vs Traditional app
      • Командная строка
    • 📎QA for SA
      • Postman | Insomnia
      • Swagger
      • Верификация vs Валидация
      • Идентификация/Аутентификация/Авторизация
    • 📎PM for SA
      • Метрики
        • Метрики привлечения
        • Метрики вовлечённости
          • ARPU
          • LTV
          • NPV
          • ROI
          • NPS
      • Прокси метрики
      • Дерево метрик
      • Фреймворки
      • Юнит-экономика
      • Модель Кано
  • Другое
    • Литература
    • Советы по составлению резюме
    • Общие вопросы на собеседовании
    • Вопросы которые надо задать интервьюеру
  • Контакты
Powered by GitBook
On this page
  • Индексы в таблицах
  • Алгоритмы индексирования
  • B-дерево

Was this helpful?

  1. Hard skills
  2. Базы данных

Оптимизация БД

Добавь базе скорость

PreviousМасштабирование БДNextТипы индексов

Last updated 4 months ago

Was this helpful?

Индексы в таблицах

Индексирование баз данных — это техника, повышающая скорость и эффективность запросов к базе данных. Она создаёт отдельную структуру данных, сопоставляющую значения в одном или нескольких столбцах таблицы с соответствующими местоположениями на физическом накопителе, что позволяет базе данных быстро находить строки по конкретному запросу без необходимости сканирования всей таблицы.

Применяются разные типы индексов, однако они занимают пространство и должны обновляться при изменении данных. Важно тщательно продумывать стратегию индексирования базы данных и регулярно её оптимизировать.

Алгоритмы индексирования

Как говорилось выше, существует множество алгоритмов индексирования, используемых для оптимизации скорости операций получения данных при помощи создания индексов столбцов таблиц. Вот некоторые из самых популярных алгоритмов индексирования баз данных:

  • B-дерево

  • Bitmap-индекс

  • Хэш-индекс

  • GiST (Generalized Search Tree, обобщённое поисковое дерево)

  • Полнотекстовый индекс

Рассмотрим самый простой и распростаненный способ индексирования - В-дерево.

B-дерево

Перед нами B-дерево индекса, присвоенного полю в таблице (которое чаще всего используется при выборках). В каждом узле хранятся элементы со значениями.Также элементы хранят ссылку на строку в таблице.

Поиск начинается с корневого узла. Наша задача — пройти по каждому элементу в узле и сравнить его значение с искомым:

  • Если значение совпало — берём ссылку на данные и читаем их из таблицы.

  • Если наше значение больше, чем значение в элементе, — идём дальше.

  • Если искомое значение меньше, чем в элементе, — нам нужно перейти в поддерево, которое хранится левее от ячейки. Далее мы попадаем на следующий уровень и итерация повторяется.

Рассмотрим алгоритм на примере поиска значения 2001.

  • Как и говорилось ранее, мы начинаем с корневого узла — первой ячейки со значением 1000.

  • Так как 2001 больше 1000, то мы идём дальше.

  • Доходим до ячейки 3000. Но 2001 меньше, чем 3000, поэтому переходим на поддерево.

  • Первая ячейка идёт со значением 2200, наше значение меньше, значит снова переходим на левое поддерево.

  • И сразу же находим ячейку со значением 2001.

То, что мы и искали. А так как искомая ячейка содержит ссылку на место, где лежат наши данные, то мы можем легко и быстро прочитать их.

Источники:

(почитать!)

📍
https://habr.com/ru/companies/ruvds/articles/724066/
https://skillbox.ru/media/code/kak_uskorit_bazu_dannykh_s_pomoshchyu_indeksov/
https://otus.ru/journal/vse-chto-neobhodimo-znat-pro-indeksy-ms-sql/
Поиск значения 2001