Развитие баз данных

Простые и структурированные файлы

Модель данных простого файла

Самая простая форма организации данных в базе, соответственно, была создана одной из первых. Из-за своей простоты имеет множество недостатков, однако до сих пор используется во многих областях.

Структура

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

• Заголовок (названия столбцов)
• Данные (просто текст)

Пример

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

ФИО,Предмет,Оценка
Иванов И.И.,Java,4
Иванов И.И.,Базы данных,5
Петров П.П.,Java,5
Петров П.П.,Базы данных,4

Модель данных структурированного файла

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

Структура

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

• Заголовок (названия столбцов, типы и длины)
• Данные (записи одинаковой структуры)

Пример

Здесь к строке, содержащей заголовки, добавляется дополнительная строка с типами и длинами. В данном формате цифра обозначает количество символов для этого поля.

ФИО           Предмет     Оценка
String, 14    String, 12  Number, 1
Иванов И.И.   Java          4
Иванов И.И.   Базы данных   5
Петров П.П.   Java          5
Петров П.П.   Базы данных   4

Достоинства

• Простота чтения (так как данные можно просто читать построчно)

Недостатки

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

Реализации

• Данные на перфокартах
• dBase
• Excel / LibreOffice Calc

Файловые системы

Файловая модель данных

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

Представление данных

Имеем структуру из каталогов и файлов, лежащих внутри. В файлы можем заносить не только сами данные, но и некоторые ограничения на них.

• Файл – одна запись (одноуровневая структура)
• Каталоги – подчиненные записи

Пример

Здесь через символ / обозначено разделение на подкаталоги, у которых внутри лежат файлы с некоторыми конкретными для каждого случая данными. Данные в файле так же могут быть структурированными.

• Иванов И.И./Данные – ФИО, адрес, etc
• Иванов И.И./Оценки/Java – 4
• Иванов И.И./Оценки/Базы данных – 5
• Петров П. П./Данные – ФИО, адрес, etc
• Иванов П. П./Оценки/Java – 5
• Петров П. П./Оценки/Базы данных – 4

Достоинства

• Структурирование данных (у нас есть опция хранения в файлах дополнительной информации о данных)
• Простота реализации (мы используем для реализации готовую файловую систему)

Недостатки

• Сложно извлекать требуемые данные (в примере сложно посчитать среднюю оценку по предмету)
• Нет проверки целостности (но можно, например, добавить проверку уникальности)
• Большое количество файлов (не все файловые системы такое потянут с приемлимой производительностью)

Реализации

• FATx, ExtX, NTFS, APFS
• DOM

Иерархические базы данных

Иерархическая модель данных

Заметим, что работа файловых систем с большим количеством файлов оказывается на практике слишком дорогой. Тогда появляется идея построить иерархию самостоятельно. Такая модель является совокупностью взаимосвязанных объектов, cвязь двух объектов отражает их подчиненность. Иерархия это полезно, но складывать это в файловую систему не очень эффективно. Предложена и реализована IBM в 1966.

Представление данных

Теперь мы храним дерево записей, при этом для каждой записи мы знаем ее тип и структуру. Таким образом исчезает проблема с ошибками в типах хранящихся данных. Так же для каждой записи имеет произвольное количество подчиненных записей (детей).

• Дерево записей
• Отношения родитель – ребенок (как каталоги и подкаталоги)

Пример

Здесь в рамочки обведены узлы дерева, где мы храним сами данные и их тип, а стрелочками обозначены отношения родитель-ребенок.

Достоинства

• Проверка целостности записей и отношений (можем проверять отдельные поля записей при сохранении, записи целиком, описанные в структуре отношения, также можем разрешать добавлять дубликаты, где необходимо)
• Последовательное расположение записей (таким образом мы оптимизируем последовательный доступ к данным, что оптимизирует некоторые запросы)
• Эффективность реализации (за счет группировки данных одного типа)

Недостатки

• Представление только древовидных данных (например отношение многие ко многим требует от нашей модели обратного ссылок, которые невозможно обеспечить в древовидной структуре)
• Существенно меняющееся время запроса в отношении многие-ко-многим в зависимости от того, кто выше в иерархии. Можно хранить две версии, однако возникает проблема с их согласованием, то есть в этот момент мы начинаем допускать некорректные данные.

Реализации

• IBM Information Management System
• Windows registry

Сетевые базы данных

Сетевая модель данных

Отсутствие отношения многие ко многим очень сильно затрудняет реализацию разумных запросов в иерархической модели даных. Для решения этой проблемы была предложена сетевая модель данных. Эта модель также является совокупностью взаимосвязанных объектов, однако здесь нет единой строгой иерархии, то есть могут существовать дополнительные с более низкой эффективностью поиска. Таким образом сетевые модели данных по сравнению с иерархическими являются более универсальными. Предложена CODASYL в 1969.

Представление данных

• Ориентированный граф записей
• Отношения владелец – запись

Пример

Достоинства

• Представление всех типов связей
• Возможность описания структуры
• Эффективность реализации (сильно меняется от основной иерархии к дополнительной)

Недостатки

• Сложность реализации
• Жесткое ограничение структуры

Реализации

• Integrated Data Store
• Integrated Database Management System
• TurboIMAGE

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

Реляционная модель данных

Самая популярная на данный момент модель данных. Отличается от предыдущих моделей заданием связей непосредственно в запросах, а также наличием математической модели, позволяющей оптимизировать эти запросы. Предложена Э. Ф. Коддом в 1969.

Структура

• Данные хранятся в таблицах
• Проверка целостности заданных связей
• Связи задаются в запросах

Пример

Достоинства

• Представление всех типов связей
• Гибкая структура данных
• Математическая модель (благодаря этому можем находить более эффективные эквивалентные запросы)

Недостатки

• Сложность реализации
• Сложность представления иерархических данных
• Сложность составления эффективных запросов (сильно зависит от оптимизатора)

Реализации

• Oracle Database
• SQLite

Объектные базы данных

Объектная модель данных

Уметь хранить графы объектов в памяти очень полезно. Предложена в 1985. Сейчас такие базы данных в основном реализуются через слой трансляции в реляционную базу.

Структура

• Сущность – объект
• Связь – поле
• Ограничения целостности – определение объекта

Пример

Достоинства

• Простота представления объектов (из-за ориентированности модели данных на данную задачу)
• Гибкая структура данных (так как можем хранить произвольные обьекты)
• Логичное направление ссылок (соответственно направлению в объектах)

Недостатки

• Сложность реализации (так как стандартный способ - трансляция в реляционную модель)
• Сложность миграции схемы (что будет с объектами в базе, если мы захотим добавить им поле)
• Малая распространенность

Реализации

• Oracle Database Objects
• ObjectDB

NoSQL

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

Мы можем быстро искать документы с произвольным содержанием.

Представление данных

• Слабоструктурированные документы
  • XML
  • JSON
• Выборка по свойствам

Пример

Ключ-значение

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

Представление данных

• Ключ
• Произвольное значение

Пример

Другие

Табличные

Если у нас отсутствуют сложные взаимосвязи между данными, мы можем хотеть оптимизировать использование одной большой таблицы.

• Одна большая таблица
• Хранится построчно

Столбчатые

Представим, что запись у нас содержит множество столбцов. Нужно ли нам каждый раз читать их все, как происходит в традиционном подходе? В таком случае нам выгодно хранить столбцы отдельно друг от друга.

• Одна большая таблица
• Хранится по столбцам

Графовые

Часто мы можем захотеть хранить графы объектов. Один из примеров - социальные сети.

• Граф объектов
• Данные в узлах
• Данные на ребрах

Достоинства

• Большой выбор (можем любое свойство предыдущих моделей обменивать на производительность)
• Гибкость (возникают проблемы, если появляется незапланированный сценарий использования)
• Скорость работы (но зависит от реализации)

Недостатки

• Множество вещей делается в коде (который надо будет проверять, поддерживать и обновлять)
• Нет оптимизатора
• Легко ошибиться (так как большинство вещей делается в коде)