Что хранится в файлах реляционной базы данных ответ
Как организована информация в реляционной базе данных
Структура реляционных баз данных
Основные термины и понятия реляционных баз данных представлены:
Файлы реляционной базы данных имеют свои особенности:
Организация информации в реляционной базе данных
Информация в реляционной базе данных организуется по следующему принципу: пары таблиц объединяются между собой при помощи совпадающих ключей (одинаковых столбцов), которые называются информационными связями. Выделяют информационные связи трех типов:
Чаще всего при работе с БД выполняются три основных правила нормализации, что относит базу данных к:
Благодаря такой организации сокращается объем избыточных данных в БД, уменьшаются затраты на ее ведение, устраняется противоречивость хранимой в базе информации и обеспечивается ее безопасность.
Узнать более подробно об организации информации в реляционных базах данных все желающие смогут в рамках профессиональной подготовки по курсу «Инструментальные средства бизнес-аналитики», которую проводит ВШБИ НИУ ВШЭ. Записаться на обучение по данному курсу можно на нашем сайте.
Особенности реляционных БД
БД используются для организации хранения данных. Структура реляционной базы данных полностью определяется перечнем названия полей с указанием их типов и свойств. Все записи имеют одинаковые поля, но в них показываются разные свойства объекта. Аналогом реляционной БД считается двумерная таблица. Характерные особенности файла БД:
Реляционная БД чаще всего не ограничивается одной таблицей. Обычно создаются несколько таблиц со связанной информацией. Это позволяет исполнять более сложные операции над данными. Таблицы реляционной БД обязаны соответствовать требованиям понятия нормализации отношений, то есть ограничениям на формирование, которые позволят избежать дублирования и обеспечат непротиворечивость хранимой информации. Пусть создана таблица «Прокат», содержащая следующие поля: Шифр Клиента, Ф. И. О., Вид устройства, Дата выдачи, Оплата, Срок возврата. Эта организация хранения информации имеет несколько недостатков:
Для устранения этих недостатков необходима нормализация с разделением данных на разные таблицы.
Связывание таблиц
Для любой таблицы реляционной БД задаётся первичный ключ (primary key) — поле или сочетание полей, которые определяют каждую запись. Внешний или вторичный ключ (foreign key) — это одно или несколько полей, ссылающихся на поле primary key другой таблицы.
Составной ключ называется так, потому что создаётся из нескольких полей. При образовании составных ключей не рекомендуется включать в них поля, значения которых точно определяют запись. Например, не следует образовывать ключ, в котором находятся вместе поля «номер паспорта» и «шифр клиента», потому что оба эти атрибута однозначно определяют запись. Поля с повторяющимися в таблице значениями тоже нельзя делать составной частью ключа. По значению ключа возможно найти только одну запись.
Ячейка — это наименьший структурный элемент, который задаёт определённое значение соответствующего поля. Таблицы связываются друг с другом, и поэтому данные могут выбираться сразу из нескольких таблиц. Связь создаётся, если в них присутствуют одинаковые поля. Типы связей:
Связи «один к одному» встречаются довольно редко. «Один ко многим» применяются чаще, например, кассир продаёт много билетов. «Многие ко многим» тоже встречаются часто. Например, студент изучает много предметов. Связи «многие ко многим» нельзя организовывать непосредственно. Для установления отношения необходимо сопоставить каждому primary key внешний ключ, который представляет собой primary key другой таблицы. Реляционные системы базируются на теории реляционной модели, которая включает в себя три аспекта:
Управление созданием и использованием БД осуществляется системами управления базами данных (СУБД).
Под их руководством:
Для проведения этих операций организуются запросы. Итогом выполнения запросов будут либо изменения в таблицах, либо получение таблицы данных. При этом поддерживается принцип безопасности информации. Для реляционной БД основным языком управления является SQL.
Стадии и пример проектирования хранилища
Приступая к созданию базы, разработчик составляет для объектов манипулирования и их связей представление в терминах реляционной БД (таблицы, поля, записи). Проектирование проходит несколько стадий:
Преимущества этой модели данных состоят в том, что информация отображается в удобной для пользователя форме, а для манипуляций используется развитой математический аппарат.
Примером реляционной базы данных может послужить проект оптимизации деятельности пункта проката. Требуется автоматизировать такие процедуры: учёт клиентов; регистрацию инвентаря, выданного в прокат; отслеживание даты выдачи, сроков возврата, оплаты; получение информации по этим позициям; формирование отчёта по задолженностям. Реляционная БД может быть задана в виде трёх связанных таблиц.
Используя имеющиеся данные, следует определить отношения и объекты этих отношений. Объектами будут являться клиенты и устройства. Отношения между ними состоят в том, что каждый клиент может брать в прокат одно или несколько устройств.
Атрибутами для сопоставления объектов друг другу должны выступать ячейки с уникальным содержимым. В таблицах есть по одному полю с уникальными данными. В № 1 «Клиент» — это шифр клиента, а в № 3 «Склад» — шифр устройства. Это и будут primary keys. Каждая строка таблицы «Прокат» будет связывать два внешних ключа между собой:
Проблемы модели
Преимущество реляционных хранилищ состоит в том, что они способны обеспечить наилучшее соотношение устойчивости, производительности, гибкости, совместимости и масштабируемости. Реляционные БД предоставляют лёгкий доступ к составляемым отчётам и обеспечивают высокую надёжность и целостность информации из-за отсутствия избыточных данных. Но сейчас, когда всё большее количество приложений работает с высокой нагрузкой, увеличивается значение фактора масштабируемости.
Реляционные БД легко масштабируются, только когда они расположены на одном сервере. Если потребуется увеличить количество серверов и разделить нагрузку между ними, то возрастёт сложность хранилищ, что значительно снизит возможность использовать их как платформу для мощных распределённых систем. Поэтому приходится применять другие типы БД, которые обладают лучшей масштабируемостью и отказываться от возможностей, предоставляемых реляционными хранилищами.
Реляционная БД — это совокупность связей, которые способны структурировать данные, что даёт возможность рационального хранения и эффективного использования информационных материалов.
Как работают реляционные базы данных (Часть 1)
Привет, Хабр! Представляю вашему вниманию перевод статьи
«How does a relational database work».
Когда дело доходит до реляционных баз данных я не могу не думать, что чего-то не хватает. Они используются везде. Существует множество различных баз данных: от небольшого и полезного SQLite до мощной Teradata. Но есть только несколько статей, которые объясняют, как работает база данных. Вы можете искать сами по запросу «howdoesarelationaldatabasework» («как работают реляционные базы данных») чтобы увидеть, как мало результатов. Более того, эти статьи — короткие. Если же вы ищете последние модные технологии (BigData, NoSQL или JavaScript), вы найдете больше углубленных статей, объясняющих, как они работают.
Являются ли реляционные базы данных слишком старыми и слишком скучными, чтобы их можно было объяснить вне университетских курсов, исследовательских работ и книг?
Как разработчик я ненавижу использовать то, что не понимаю. И если базы данных используются в течение более чем 40 лет, должна быть причина. За эти годы я потратил сотни часов, чтобы по-настоящему понять эти странные черные ящики, которые я использую каждый день. Реляционные базы данных очень интересны, потому что они основаны на полезных и многократно используемых концепциях. Если вас интересует понимание базы данных, но у вас никогда не было времени или желания копаться в этой широкой теме, вам должна понравиться эта статья.
Хотя название этой статьи является явным, цель этой статьи не в том, чтобы понять, как использовать базу данных. Следовательно, вы уже должны знать, как написать простой запрос соединения и базовые запросы CRUD; иначе вы можете не понять эту статью. Это единственное, что вам нужно знать, я объясню все остальное.
Начну с некоторых основ компьютерных наук, таких как временная сложность алгоритмов (BigO). Я знаю, что некоторые из вас ненавидят эту концепцию, но без нее вы не сможете понять тонкости внутри базы данных. Поскольку это огромная тема, я сосредоточусь на том, что считаю важным: как база данных обрабатывает SQL запрос. Я представлю только основные концепции базы данных, чтобы в конце статьи вы имели представление о том, что происходит под капотом.
Поскольку это длинная и техническая статья, которая включает в себя множество алгоритмов и структур данных, не торопитесь, чтобы прочитать ее. Некоторые концепции могут быть сложны для понимания; вы можете пропустить их и все равно получить общее представление.
Для более осведомленных из вас, эта статья разделена на 3 части:
Возвращаясь к основам
Много лет назад (в далекой, далекой галактике. ), разработчики должны были точно знать количество операций, которые они кодировали. Они знали наизусть свои алгоритмы и структуры данных, потому что не могли позволить себе тратить ЦП и память своих медленных компьютеров.
В этой части я напомню вам о некоторых из этих концепций, поскольку они необходимы для понимания базы данных. Я также введу понятие индекса базы данных.
O(1) vs O(n 2 )
В настоящее время многие разработчики не заботятся о временной сложности алгоритмов … и они правы!
Но когда вы имеете дело с большим количеством данных (я не говорю о тысячах) или если вы боретесь за миллисекунды, становится критически важным понять эту концепцию. И как вы понимаете, базы данных должны иметь дело с обеими ситуациями! Я не заставлю вас потратить больше времени, чем необходимо чтобы ухватить суть. Это поможет нам позже понять концепцию оптимизации на основе затрат (cost based optimization).
Концепция
Временная сложность алгоритма используется, чтобы увидеть сколько времени займет выполнение алгоритма для данного объема данных. Чтобы описать эту сложность, используют математические обозначения больших О. Эта нотация используется с функцией, которая описывает, сколько операций нужно алгоритму для заданного количества входных данных.
Например, когда я говорю «этот алгоритм имеет сложность O (some_function() )», это означает, что для обработки определенного объема данных алгоритму требуется some_function(a_certain_amount_of_data) операций.
При этом важно не количество данных**, а то, ** как увеличивается количество операций при увеличении объема данных. Сложность по времени не дает точное количество операций, но хороший способ для оценки времени выполнения.
На этом графике вы можете увидеть зависимость числа операций от объема входных данных для различных типов временных сложностей алгоритмов. Я использовал логарифмическую шкалу, чтобы отобразить их. Другими словами, количество данных быстро увеличивается с 1 до 1 млрд. Мы можем увидеть, что:
Примеры
При небольшом количестве данных разница между O(1) и O(n 2 ) незначительна. Например, предположим, что у вас есть алгоритм, который должен обрабатывать 2000 элементов.
Разница между O(1) и O(n 2 ) кажется большой (4 миллиона операций) но вы потеряете максимум 2 мс, просто время моргнуть глазами. Действительно, современные процессоры могут обрабатывать сотни миллионов операций в секунду. Вот почему производительность и оптимизация не являются проблемой во многих ИТ-проектах.
Как я уже сказал, по-прежнему важно знать эту концепцию при работе с огромным количеством данных. Если на этот раз алгоритм должен обработать 1 000 000 элементов (что не так уж много для базы данных):
Я не делал расчетов, но я бы сказал, что с помощью алгоритма O (n2) у вас есть время выпить кофе (даже два!). Если вы добавите еще 0 к объему данных, у вас будет время, чтобы вздремнуть.
Идем глубже
Примечание: в следующих частях мы увидим эти алгоритмы и структуры данных.
Есть несколько типов временной сложности алгоритма:
Временная сложность часто является наихудшим сценарием.
Я говорил только о временной сложности алгоритма, но сложность также применима для:
Примечание: я дал вам не реальное определение обозначения «большой О», а просто идею. Вы можете прочитать эту статью в Википедии для реального (асимптотического) определения.
MergeSort (Сортировка слиянием)
Что вы делаете, когда вам нужно отсортировать коллекцию? Что? Вы вызываете функцию sort ()… Ок, хороший ответ… Но для базы данных вы должны понимать, как работает эта функция sort ().
Существует несколько хороших алгоритмов сортировки, поэтому я остановлюсь на самом важном: сортировке слиянием. Возможно, вы сейчас не понимаете, почему сортировка данных полезна, но вы должны будете понять, после части посвященной оптимизации запросов. Более того, понимание сортировки слиянием поможет нам позже понять общую операцию join баз данных, называемую merge join (объединение слиянием).
Merge (слияние)
Как и многие полезные алгоритмы, сортировка слиянием основана на хитрости: объединение 2 отсортированных массивов размера N / 2 в N-элементный отсортированный массив стоит всего N операций. Эта операция называется слиянием.
Давайте посмотрим, что это значит на простом примере:
На этом рисунке видно, что для построения окончательного отсортированного массива из 8 элементов вам нужно всего лишь выполнить итерацию один раз в 2х 4-элементных массивах. Поскольку оба 4-элементных массива уже отсортированы:
Это работает, потому что оба 4-элементных массива отсортированы, и поэтому вам не нужно «возвращаться» в этих массивах.
Теперь, когда мы поняли этот трюк, вот мой псевдокод для merge:
Сортировка слиянием разбивает задачу на меньшие задачи, а затем находит результаты меньших задач, чтобы получить результат исходной задачи (примечание: этот вид алгоритмов называется разделяй и властвуй). Если вы не понимаете этот алгоритм, не волнуйтесь; я не понял этого в первый раз, когда увидел. Если это может помочь вам, я вижу этот алгоритм как двухфазный алгоритм:
Division phase (фаза деления)
На этапе деления массив делится на унитарные массивы за 3 шага. Формальное количество шагов — log(N) (поскольку N=8, log(N) = 3).
Я гений! Одним словом — математика. Идея состоит в том, что каждый шаг делит размер исходного массива на 2. Количество шагов — это количество раз, которое вы можете разделить исходный массив на два. Это точное определение логарифма (с основанием 2).
Sorting phase (Фаза сортировки)
На этапе сортировки вы начинаете с унитарных (одноэлементных) массивов. В течение каждого этапа вы применяете несколько операций слияния, и общая стоимость составляет N = 8 операций:
Поскольку существует log (N) шагов, общая стоимость N * log(N) операций.
Преимущества merge sort
Почему этот алгоритм такой мощный?
Примечание: этот вид алгоритмов называется in-place (сортировка без дополнительной памяти).
Примечание: этот вид алгоритмов называется внешняя сортировка.
Например, распределенная сортировка слиянием является одним из ключевых компонентов Hadoop (который является структурой в больших данных).
Этот алгоритм сортировки используется в большинстве (если не во всех) базах данных, но он не единственный. Если вы хотите узнать больше, вы можете прочитать эту исследовательскую работу, которая обсуждает плюсы и минусы общих алгоритмов сортировки в базе данных.
Массив, Дерево и Хеш-таблица
Теперь, когда мы понимаем идею временной сложности и сортировки, я должен рассказать вам о 3 структурах данных. Это важно, потому что они являются основой современных баз данных. Я также введу понятие индекса базы данных.
Массив
Двумерный массив — простейшая структура данных. Таблицу можно рассматривать как массив. Например:
Этот 2-мерный массив представляет собой таблицу со строками и столбцами:
Так удобно хранить и визуализировать данные однако, когда вам нужно найти определенное значение, это не подходит.
Например, если вы хотите найти всех ребят, которые работают в Великобритании, вам нужно будет просмотреть каждую строку, чтобы определить, принадлежит ли эта строка к Великобритании. Это будет стоить вам N операций, где N — количество строк, что неплохо, но может ли быть более быстрый путь? Теперь нам пришло время познакомится с деревьями.
Примечание: большинство современных баз данных предоставляют расширенные массивы для эффективного хранения таблиц: heap-organizedtables и index-organizedtables. Но это не меняет проблему быстрого поиска определенного условия в группе столбцов.
Дерево и индекс базы данных
Двоичное дерево поиска — это двоичное дерево со специальным свойством, ключ в каждом узле должен быть:
Давайте посмотрим, что это значит визуально
Это дерево имеет N = 15 элементов. Допустим, я ищу 208:
В итоге оба поиска обойдутся мне в количество уровней внутри дерева. Если вы внимательно прочитаете часть о сортировке слиянием, вы должны увидеть, что здесь log (N) уровней. Получается, стоимость поиска log(N), не плохо!
Возвращаемся к нашей проблеме
Но это очень абстрактно, поэтому давайте вернемся к нашей проблеме. Вместо простого integer, представьте строку, которая представляет страну кого-то в предыдущей таблице. Предположим, у вас есть дерево, которое содержит поле «country» (column 3) таблицы:
Этот поиск будет стоить log(N) операций вместо N операций если вы напрямую будете использовать массив. То, что вы только что представили — это был индекс базы данных.
Вы можете построить индексное дерево для любой группы полей (строка, число, 2 строки, число и строка, дата …) до тех пор, пока у вас есть функция для сравнения ключей (т.е. групп полей) так что вы можете установить порядок среди ключей (что имеет место для любых основных типов в базе данных).
B+TreeIndex
Хотя это дерево хорошо работает для получения определенного значения, существует БОЛЬШАЯ проблема, когда вам нужно получить несколько элементов между двумя значениями. Это будет стоить O(N) потому что вам придется посмотреть на каждый узел в дереве и проверить, находится ли он между этими двумя значениями (например, с упорядоченным обходом дерева). Более того, эта операция не удобна для дискового ввода-вывода, так как вам придется читать полное дерево. Нам нужно найти способ эффективно выполнить запрос диапазона. Для решения этой проблемы современные базы данных используют модифицированную версию предыдущего дерева под названием B+Tree. В B+Tree дереве:
Как вы можете видеть, здесь узлов больше (в два раза). Действительно, у вас есть дополнительные узлы, «узлы принятия решений», которые помогут вам найти правильный узел (который хранит расположение строк в связанной таблице). Но сложность поиска все еще O(log(N)) (есть только еще один уровень). Большая разница состоит в том, что ноды на нижем уровне связаны с их преемниками.
С этим B+Tree, если вы ищете значения от 40 до 100:
Допустим, вы нашли M преемников, и дерево имеет N узлов. Поиск конкретного узла стоит log(N) подобно предыдущему дереву. Но, получив этот узел, вы получите M преемников в M операциях со ссылками на их преемников. Этот поиск стоит только M+log(N) операций по сравнению с N операций с предыдущим деревом. Более того, вам не нужно читать полное дерево (только M + log (N) узлов), что означает меньшее использование диска. Если М мало (например, 200 строк) и N большой (1 000 000 строк), это будет БОЛЬШАЯ разница.
Но здесь есть новые проблемы (снова!). Если вы добавляете или удаляете строку в базе данных (и, следовательно, в связанном индексе B+Tree):
Другими словами, B+Tree должно быть самоупорядоченным и сбалансированным. К счастью, это возможно с умными операциями удаления и вставки. Но это обходится дорого: вставка и удаление в дереве B+ обходятся в O (log (N)). Вот почему некоторые из вас слышали, что использование слишком большого количества индексов не очень хорошая идея. Действительно, вы замедляете быструю вставку / обновление / удаление строки в таблице, поскольку базе данных необходимо обновить индексы таблицы с помощью дорогостоящей операции O (log (N)) для каждого индекса. Более того, добавление индексов означает большую нагрузку для менеджера транзакций (будет описан в конце статьи).
Для более подробной информации, вы можете посмотреть статью в Википедии о B+Tree. Если вы хотите пример реализации B+Tree в базе данных, посмотрите эту статью и эту статью от ведущего разработчика MySQL. Они оба сосредоточены на том, как InnoDB (движок MySQL) обрабатывает индексы.
Примечание: читатель сказал мне что, из-за низкоуровневых оптимизаций дерево B+ должно быть полностью сбалансировано.
Hashtable (Хеш-таблица)
Наша последняя важная структура данных — это хеш-таблица. Это очень полезно, когда вы хотите быстро искать значения. Более того, понимание хеш-таблицы поможет нам позже понять общую операцию соединения с базой данных, называемую хеш-соединением ( hash join). Эта структура данных также используется базой данных для хранения некоторых внутренних вещей (например, таблица блокировки или буферный пул, мы увидим обе эти концепции позже).
Хеш-таблица — это структура данных, которая быстро находит элемент по его ключу. Для построения хеш-таблицы вам нужно определить:
Простой пример
Давайте возьмем наглядный пример:
Эта хеш-таблица имеет 10 сегментов. Поскольку я ленивый, я изобразил только 5 сегментов, но я знаю, что вы умные, поэтому позволю вам представить 5 других самостоятельно. Я использовал хэш-функцию по модулю 10 ключа. Другими словами, сохраняю только последнюю цифру ключа элемента, чтобы найти его сегмент:
Функция сравнения, которую я использовал, это просто равенство между двумя целыми числами.
Допустим, вы хотите получить элемент 78:
Теперь, допустим, вы хотите получить элемент 59:
Хорошая хеш-функция
Как видите, в зависимости от значения, которое вы ищете, стоимость не одинакова!
Если я теперь изменю хэш-функцию по модулю 1 000 000 от ключа (то есть, взяв последние 6 цифр), второй поиск будет стоить только 1 операцию, поскольку в сегменте 000059 нет элементов. Реальная задача — найти хорошую хэш-функцию, которая будет создавать сегменты, содержащие очень небольшое количество элементов.
В моем примере найти хорошую хеш-функцию легко. Но это простой пример, найти хорошую хеш-функцию сложнее, когда ключ:
С хорошей хеш-функцией поиск в хеш-таблице обходится в O(1).
Массив vs хеш-таблица
Почему бы не использовать массив?
Для дополнительной информации, вы можете прочитать статью о JavaHashMap, которая является эффективной реализацией хеш-таблицы; вам не нужно понимать Java, чтобы понять концепции, изложенные в этой статье.