Базы данных: типы & реализация

Исследуйте ключевые модели данных, их архитектуру и способы реализации — от классических реляционных до современных графовых и NoSQL-решений.

Реляционные базы данных (RDBMS)

Данные организованы в виде таблиц (отношений) со строго заданной схемой. Связи между таблицами реализуются через внешние ключи. SQL — стандартный язык запросов. Обеспечивают ACID-транзакции и целостность.

Примеры СУБД

  • PostgreSQL, MySQL, Oracle, Microsoft SQL Server, SQLite

Особенности

  • Строгая схема (DDL)
  • Поддержка JOIN, индексов, представлений
  • Нормализация для устранения избыточности

Способы реализации

  • Хранение: B-деревья, кучи (heap), кластеризованные индексы.
  • Обработка запросов: оптимизатор на основе статистики, конвейерные алгоритмы.
  • Транзакции: MVCC (многоверсионность), двухфазная фиксация, WAL-журналирование.
  • Язык: SQL + расширения (PL/pgSQL, T-SQL).

Ключевые механизмы реализации

СУБД используют буферный кэш, планировщик запросов, синхронизацию блокировок (row-level locking) и контроль конкурентности. Современные решения (PostgreSQL) реализуют параллельное выполнение запросов, секционирование и репликацию master-slave / multi-master.

ACID SQL:1999+ Индексы B-Tree / Hash

Документоориентированные БД

Хранят данные в виде полуструктурированных документов (JSON, BSON, XML). Схема гибкая, каждая запись может иметь свой набор полей. Отлично подходят для иерархических данных и быстрого прототипирования.

Популярные системы

  • MongoDB, Couchbase, Firestore, Amazon DocumentDB

Сильные стороны

  • Горизонтальное масштабирование (sharding)
  • Высокая скорость записи/чтения
  • Естественное отображение на объекты ООП

Способы реализации

  • Формат хранения: BSON (MongoDB) или плоские файлы с индексами.
  • Индексация: вторичные индексы, полнотекстовый поиск, geospatial.
  • Шардирование по ключу документа, автоматическая балансировка.
  • Язык запросов: API-запросы (JSON), агрегационные конвейеры.

Архитектурные особенности

Документные БД используют LSM-деревья или MMAP для эффективной работы. Реализуют eventual consistency (в конфигурациях с репликами) либо сильную согласованность. MongoDB использует движок WiredTiger с поддержкой транзакций на нескольких документах.

Гибкая схема MapReduce Агрегации

Key-Value хранилища

Простейшая модель: ассоциативный массив (хэш-таблица). Значение — непрозрачный набор байт (строки, объекты). Минимальная задержка, высокая производительность. Идеальны для кэшей, сессий, очередей.

Известные решения

  • Redis, Memcached, Amazon DynamoDB (режим KV), Riak, etcd.

Применение

  • Кэширование, управление сессиями, счётчики, рейтинги, pub/sub.

Способы реализации

  • In-memory с persistence (Redis: RDB, AOF).
  • Хэш-индексы, LSM-деревья (RocksDB, LevelDB).
  • Распределённые реализации: consistent hashing, gossip-протоколы.
  • Поддержка TTL (время жизни ключа), атомарные операции инкремента.

Ключевые техники реализации

Для персистентности используют write-ahead log и периодические снэпшоты. В кластерах (Dynamo, Riak) реализуются векторные часы для разрешения конфликтов, репликация N=3, Quorum-алгоритмы. Redis поддерживает Lua-скрипты и модули для расширения.

O(1) чтение Горизонт. масштаб.

Колоночные (Column-Family) БД

Хранят данные по столбцам, а не по строкам. Оптимизированы для аналитических запросов и агрегаций на больших объёмах. Позволяют сжимать однородные данные и достигать высокой производительности чтения выбранных атрибутов.

Примеры

  • Apache Cassandra, HBase, Google BigTable, ClickHouse (гибрид)

Характеристики

  • Высокая плотность сжатия
  • Эффективные сканирования подмножества колонок
  • Семейства столбцов (динамические колонки)

Способы реализации

  • SSTable + MemTable (LSM-деревья) для Cassandra/HBase.
  • Распределённое хранение на HDFS / собственные файлы.
  • Партиционирование по ключу строки + кластеризация столбцов.
  • Тюнинг компрессии (ZSTD, LZ4, Snappy).

Архитектура и особенности

Cassandra использует consistent hashing (кольцо) и gossip для обнаружения узлов, tunable consistency. ClickHouse для аналитики реализует векторные вычисления и колоночные сжатые части. Такие БД отлично подходят для IoT, временных рядов и OLAP-кубов.

Высокое сжатие OLAP-дружелюбные

Графовые базы данных

Моделируют связи между сущностями как граф: вершины (узлы) и рёбра (отношения). Оптимальны для социальных сетей, рекомендательных систем, сетевой аналитики, поиска путей.

Известные реализации

  • Neo4j, Amazon Neptune, ArangoDB, JanusGraph, TigerGraph.

Ключевые концепции

  • Рёбра могут быть направленными/ненаправленными и иметь свойства.
  • Индексы на вершинах и рёбрах для быстрых обходов.

Способы реализации

  • Нативное хранение графа (Neo4j: "store files" для узлов/отношений).
  • Алгоритмы обхода: BFS, DFS с оптимизацией индексов (adjacency lists).
  • Распределённые решения: JanusGraph поверх Bigtable/Cassandra.
  • Языки запросов: Cypher, Gremlin, GraphQL (интеграции).

Инжиниринг графовых БД

Индексно-свободные соединения (index-free adjacency) — каждая вершина ссылается на смежные, что даёт O(1) доступ. Neo4j использует кэш страниц и транзакции ACID. В распределённых системах — секционирование графа и балансировка.

Анализ связей Pathfinding

Иерархические и сетевые БД

Исторические модели: иерархическая (дерево «предок-потомок»), сетевая (записи с множественными связями — граф произвольной структуры). Заложили основы многих современных концепций.

Иерархические СУБД

  • IBM IMS, Windows Registry, XML-базы (BaseX).

Сетевые

  • CODASYL (IDMS, Integrated Data Store).

Способы реализации

  • Иерархические: физические указатели от родителя к потомкам (наборы).
  • Сетевые: записи и наборы (set) с двунаправленными связями (owner-member).
  • Языки: DL/I (иерархический), DML сетевых моделей.
  • Навигационный доступ (программист управляет курсорами).

Современное наследие

Хотя эти системы уступили место реляционным, их идеи повлияли на XML-БД, файловые системы и графовые модели. Реализации основаны на предварительно определённых физических ссылках и иерархических путях. Используются в специфических legacy-системах.

Физическая навигация Древовидная модель

Объектно-ориентированные БД (OODBMS)

Интегрируют концепции ООП в СУБД: объекты, классы, наследование, полиморфизм. Позволяют хранить сложные структуры без ORM-отображения. Поддерживают ссылки между объектами напрямую.

Примеры

  • ObjectDB, db4o, Versant Object Database, ZODB (Python).

Преимущества

  • Естественная работа с объектами ЯП
  • Отсутствие несоответствия импедансов
  • Поддержка сложных типов, коллекций

Способы реализации

  • Сохранение объектов с идентификаторами (OID).
  • Поддержка наследования через дескрипторы классов.
  • Механизмы сборки мусора, кэширование объектов.
  • Языки запросов: OQL (Object Query Language).

Ключевые аспекты реализации

OODBMS используют страничную модель с отображением объект-кортеж, но сохраняют идентичность и навигационные ссылки. Транзакции обычно работают на уровне объектов. db4o использует файл с B-деревьями для метаданных и индексов.

Прямая навигация Наследование