- PVSM.RU - https://www.pvsm.ru -
Привет! Представляю вашему вниманию перевод статьи
"How does a relational database work" [1].
Когда дело доходит до реляционных баз данных я не могу не думать, что чего-то не хватает. Они используются везде. Существует множество различных баз данных: от небольшого и полезного SQLite до мощной Teradata. Но есть только несколько статей, которые объясняют, как работает база данных. Вы можете искать сами по запросу "howdoesarelationaldatabasework" («как работают реляционные базы данных») чтобы увидеть, как мало результатов. Более того, эти статьи — короткие. Если же вы ищете последние модные технологии (BigData, NoSQL или JavaScript), вы найдете больше углубленных статей, объясняющих, как они работают.
Являются ли реляционные базы данных слишком старыми и слишком скучными, чтобы их можно было объяснить вне университетских курсов, исследовательских работ и книг?
Как разработчик я ненавижу использовать то, что не понимаю. И если базы данных используются в течение более чем 40 лет, должна быть причина. За эти годы я потратил сотни часов, чтобы по-настоящему понять эти странные черные ящики, которые я использую каждый день. Реляционные базы данных очень интересны, потому что они основаны на полезных и многократно используемых концепциях. Если вас интересует понимание базы данных, но у вас никогда не было времени или желания копаться в этой широкой теме, вам должна понравиться эта статья.
Хотя название этой статьи является явным, цель этой статьи не в том, чтобы понять, как использовать базу данных. Следовательно, вы уже должны знать, как написать простой запрос соединения и базовые запросы CRUD; иначе вы можете не понять эту статью. Это единственное, что вам нужно знать, я объясню все остальное.
Начну с некоторых основ компьютерных наук, таких как временная сложность алгоритмов (BigO). Я знаю, что некоторые из вас ненавидят эту концепцию, но без нее вы не сможете понять тонкости внутри базы данных. Поскольку это огромная тема, я сосредоточусь на том, что считаю важным: как база данных обрабатывает SQL запрос. Я представлю только основные концепции базы данных, чтобы в конце статьи вы имели представление о том, что происходит под капотом.
Поскольку это длинная и техническая статья, которая включает в себя множество алгоритмов и структур данных, не торопитесь, чтобы прочитать ее. Некоторые концепции могут быть сложны для понимания; вы можете пропустить их и все равно получить общее представление.
Для более осведомленных из вас, эта статья разделена на 3 части:
Много лет назад (в далекой, далекой галактике...), разработчики должны были точно знать количество операций, которые они кодировали. Они знали наизусть свои алгоритмы и структуры данных, потому что не могли позволить себе тратить ЦП и память своих медленных компьютеров.
В этой части я напомню вам о некоторых из этих концепций, поскольку они необходимы для понимания базы данных. Я также введу понятие индекса базы данных.
В настоящее время многие разработчики не заботятся о временной сложности алгоритмов … и они правы!
Но когда вы имеете дело с большим количеством данных (я не говорю о тысячах) или если вы боретесь за миллисекунды, становится критически важным понять эту концепцию. И как вы понимаете, базы данных должны иметь дело с обеими ситуациями! Я не заставлю вас потратить больше времени, чем необходимо чтобы ухватить суть. Это поможет нам позже понять концепцию оптимизации на основе затрат (cost based optimization).
Временная сложность алгоритма используется, чтобы увидеть сколько времени займет выполнение алгоритма для данного объема данных. Чтобы описать эту сложность, используют математические обозначения больших О. Эта нотация используется с функцией, которая описывает, сколько операций нужно алгоритму для заданного количества входных данных.
Например, когда я говорю "этот алгоритм имеет сложность O (some_function() )", это означает, что для обработки определенного объема данных алгоритму требуется some_function(a_certain_amount_of_data) операций.
При этом важно не количество данных**, а то, ** как увеличивается количество операций при увеличении объема данных. Сложность по времени не дает точное количество операций, но хороший способ для оценки времени выполнения.
На этом графике вы можете увидеть зависимость числа операций от объема входных данных для различных типов временных сложностей алгоритмов. Я использовал логарифмическую шкалу, чтобы отобразить их. Другими словами, количество данных быстро увеличивается с 1 до 1 млрд. Мы можем увидеть, что:
При небольшом количестве данных разница между O(1) и O(n2) незначительна. Например, предположим, что у вас есть алгоритм, который должен обрабатывать 2000 элементов.
Разница между O(1) и O(n2) кажется большой (4 миллиона операций) но вы потеряете максимум 2 мс, просто время моргнуть глазами. Действительно, современные процессоры могут обрабатывать сотни миллионов операций в секунду [2]. Вот почему производительность и оптимизация не являются проблемой во многих ИТ-проектах.
Как я уже сказал, по-прежнему важно знать эту концепцию при работе с огромным количеством данных. Если на этот раз алгоритм должен обработать 1 000 000 элементов (что не так уж много для базы данных):
Я не делал расчетов, но я бы сказал, что с помощью алгоритма O (n2) у вас есть время выпить кофе (даже два!). Если вы добавите еще 0 к объему данных, у вас будет время, чтобы вздремнуть.
Для справки:
Примечание: в следующих частях мы увидим эти алгоритмы и структуры данных.
Есть несколько типов временной сложности алгоритма:
Временная сложность часто является наихудшим сценарием.
Я говорил только о временной сложности алгоритма, но сложность также применима для:
Конечно, есть сложности хуже, чем n2, например:
Примечание: я дал вам не реальное определение обозначения «большой О», а просто идею. Вы можете прочитать эту статью в Википедии [3] для реального (асимптотического) определения.
Что вы делаете, когда вам нужно отсортировать коллекцию? Что? Вы вызываете функцию sort ()… Ок, хороший ответ… Но для базы данных вы должны понимать, как работает эта функция sort ().
Существует несколько хороших алгоритмов сортировки, поэтому я остановлюсь на самом важном: сортировке слиянием. Возможно, вы сейчас не понимаете, почему сортировка данных полезна, но вы должны будете понять, после части посвященной оптимизации запросов. Более того, понимание сортировки слиянием поможет нам позже понять общую операцию join баз данных, называемую merge join (объединение слиянием).
Как и многие полезные алгоритмы, сортировка слиянием основана на хитрости: объединение 2 отсортированных массивов размера N / 2 в N-элементный отсортированный массив стоит всего N операций. Эта операция называется слиянием.
Давайте посмотрим, что это значит на простом примере:
На этом рисунке видно, что для построения окончательного отсортированного массива из 8 элементов вам нужно всего лишь выполнить итерацию один раз в 2х 4-элементных массивах. Поскольку оба 4-элементных массива уже отсортированы:
Это работает, потому что оба 4-элементных массива отсортированы, и поэтому вам не нужно «возвращаться» в этих массивах.
Теперь, когда мы поняли этот трюк, вот мой псевдокод для merge:
array mergeSort(array a)
if(length(a)==1)
return a[0];
end if
//recursive calls
[left_array right_array] := split_into_2_equally_sized_arrays(a);
array new_left_array := mergeSort(left_array);
array new_right_array := mergeSort(right_array);
//merging the 2 small ordered arrays into a big one
array result := merge(new_left_array,new_right_array);
return result;
Сортировка слиянием разбивает задачу на меньшие задачи, а затем находит результаты меньших задач, чтобы получить результат исходной задачи (примечание: этот вид алгоритмов называется разделяй и властвуй). Если вы не понимаете этот алгоритм, не волнуйтесь; я не понял этого в первый раз, когда увидел. Если это может помочь вам, я вижу этот алгоритм как двухфазный алгоритм:
На этапе деления массив делится на унитарные массивы за 3 шага. Формальное количество шагов — log(N) (поскольку N=8, log(N) = 3).
Откуда я это знаю?
Я гений! Одним словом — математика. Идея состоит в том, что каждый шаг делит размер исходного массива на 2. Количество шагов — это количество раз, которое вы можете разделить исходный массив на два. Это точное определение логарифма (с основанием 2).
На этапе сортировки вы начинаете с унитарных (одноэлементных) массивов. В течение каждого этапа вы применяете несколько операций слияния, и общая стоимость составляет N = 8 операций:
Поскольку существует log (N) шагов, общая стоимость N * log(N) операций.
Почему этот алгоритм такой мощный?
Потому что:
Примечание: этот вид алгоритмов называется in [4]- [4]place [4] (сортировка без дополнительной памяти).
Примечание: этот вид алгоритмов называется внешняя сортировка [5].
Например, распределенная сортировка слиянием является одним из ключевых компонентов Hadoop [6] (который является структурой в больших данных).
Этот алгоритм сортировки используется в большинстве (если не во всех) базах данных, но он не единственный. Если вы хотите узнать больше, вы можете прочитать эту исследовательскую работу [7], которая обсуждает плюсы и минусы общих алгоритмов сортировки в базе данных.
Теперь, когда мы понимаем идею временной сложности и сортировки, я должен рассказать вам о 3 структурах данных. Это важно, потому что они являются основой современных баз данных. Я также введу понятие индекса базы данных.
Двумерный массив — простейшая структура данных. Таблицу можно рассматривать как массив. Например:
Этот 2-мерный массив представляет собой таблицу со строками и столбцами:
Так удобно хранить и визуализировать данные однако, когда вам нужно найти определенное значение, это не подходит.
Например, если вы хотите найти всех ребят, которые работают в Великобритании, вам нужно будет просмотреть каждую строку, чтобы определить, принадлежит ли эта строка к Великобритании. Это будет стоить вам N операций, где N — количество строк, что неплохо, но может ли быть более быстрый путь? Теперь нам пришло время познакомится с деревьями.
Примечание: большинство современных баз данных предоставляют расширенные массивы для эффективного хранения таблиц: heap-organizedtables и index-organizedtables. Но это не меняет проблему быстрого поиска определенного условия в группе столбцов.
Двоичное дерево поиска — это двоичное дерево со специальным свойством, ключ в каждом узле должен быть:
Давайте посмотрим, что это значит визуально
Это дерево имеет N = 15 элементов. Допустим, я ищу 208:
Теперь, скажем, я ищу 40
В итоге оба поиска обойдутся мне в количество уровней внутри дерева. Если вы внимательно прочитаете часть о сортировке слиянием, вы должны увидеть, что здесь log (N) уровней. Получается, стоимость поиска log(N), не плохо!
Но это очень абстрактно, поэтому давайте вернемся к нашей проблеме. Вместо простого integer, представьте строку, которая представляет страну кого-то в предыдущей таблице. Предположим, у вас есть дерево, которое содержит поле "country" (column 3) таблицы:
Этот поиск будет стоить log(N) операций вместо N операций если вы напрямую будет е использовать массив. То, что вы только что представили — это был индекс базы данных.
Вы можете построить индексное дерево для любой группы полей (строка, число, 2 строки, число и строка, дата …) до тех пор, пока у вас есть функция для сравнения ключей (т.е. групп полей) так что вы можете установить порядок среди ключей (что имеет место для любых основных типов в базе данных).
Хотя это дерево хорошо работает для получения определенного значения, существует БОЛЬШАЯ проблема, когда вам нужно получить несколько элементов между двумя значениями. Это будет стоить 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 [8]+ [8]Tree [8]. Если вы хотите пример реализации B+Tree в базе данных, посмотрите эту статью [9] и эту статью [10] от ведущего разработчика MySQL. Они оба сосредоточены на том, как InnoDB (движок MySQL) обрабатывает индексы.
Примечание: читатель сказал мне что, из-за низкоуровневых оптимизаций дерево B+ должно быть полностью сбалансировано.
Наша последняя важная структура данных — это хеш-таблица. Это очень полезно, когда вы хотите быстро искать значения. Более того, понимание хеш-таблицы поможет нам позже понять общую операцию соединения с базой данных, называемую хеш-соединением ( hash join). Эта структура данных также используется базой данных для хранения некоторых внутренних вещей (например, таблица блокировки или буферный пул, мы увидим обе эти концепции позже).
Хеш-таблица — это структура данных, которая быстро находит элемент по его ключу. Для построения хеш-таблицы вам нужно определить:
Давайте возьмем наглядный пример:
Эта хеш-таблица имеет 10 сегментов. Поскольку я ленивый, я изобразил только 5 сегментов, но я знаю, что вы умные, поэтому позволю вам представить 5 других самостоятельно. Я использовал хэш-функцию по модулю 10 ключа. Другими словами, сохраняю только последнюю цифру ключа элемента, чтобы найти его сегмент:
Функция сравнения, которую я использовал, это просто равенство между двумя целыми числами.
Допустим, вы хотите получить элемент 78:
Теперь, допустим, вы хотите получить элемент 59:
Как видите, в зависимости от значения, которое вы ищете, стоимость не одинакова!
Если я теперь изменю хэш-функцию по модулю 1 000 000 от ключа (то есть, взяв последние 6 цифр), второй поиск будет стоить только 1 операцию, поскольку в сегменте 000059 нет элементов. Реальная задача — найти хорошую хэш-функцию, которая будет создавать сегменты, содержащие очень небольшое количество элементов.
В моем примере найти хорошую хеш-функцию легко. Но это простой пример, найти хорошую хеш-функцию сложнее, когда ключ:
С хорошей хеш-функцией поиск в хеш-таблице обходится в O(1).
Почему бы не использовать массив?
Хм, хороший вопрос.
Для дополнительной информации, вы можете прочитать статью о Java [11]HashMap [11], которая является эффективной реализацией хеш-таблицы; вам не нужно понимать Java, чтобы понять концепции, изложенные в этой статье.
Автор: BlackEric001
Источник [12]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/346083
Ссылки в тексте:
[1] "How does a relational database work": http://coding-geek.com/how-databases-work/
[2] сотни миллионов операций в секунду: https://ru.wikipedia.org/wiki/IPS_(%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B4%D0%B5%D0%B9%D1%81%D1%82%D0%B2%D0%B8%D0%B5)
[3] Википедии: https://ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5
[4] in: https://en.wikipedia.org/wiki/In-place_algorithm
[5] внешняя сортировка: https://ru.wikipedia.org/wiki/%D0%92%D0%BD%D0%B5%D1%88%D0%BD%D1%8F%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
[6] Hadoop: https://hadoop.apache.org/docs/stable/api/org/apache/hadoop/mapreduce/Reducer.html
[7] исследовательскую работу: http://wwwlgis.informatik.uni-kl.de/archiv/wwwdvs.informatik.uni-kl.de/courses/DBSREAL/SS2005/Vorlesungsunterlagen/Implementing_Sorting.pdf
[8] B: https://ru.wikipedia.org/wiki/B%E2%81%BA-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE
[9] эту статью: http://blog.jcole.us/2013/01/07/the-physical-structure-of-innodb-index-pages/
[10] эту статью: http://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/
[11] Java: http://coding-geek.com/how-does-a-hashmap-work-in-java/
[12] Источник: https://habr.com/ru/post/487654/?utm_source=habrahabr&utm_medium=rss&utm_campaign=487654
Нажмите здесь для печати.