Реляционный способ хранения данных

Реляционный способ хранения данных

По Вашему запросу ничего не найдено.

Рекомендуем сделать следующее:

• Проверьте правильность написания ключевых слов.
• Используйте синонимы введенных Вами ключевых слов, например “приложение” вместо “программное обеспечение”.
• Попробуйте воспользоваться одним из популярных поисковых запросов ниже.
• Начните новый поиск.

Что такое реляционная база данных?

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

Пример реляционной базы данных

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

У обеих таблиц есть только один общий элемент — идентификатор столбца (ключ). Благодаря наличию этого общего столбца реляционные базы данных могут устанавливать взаимосвязи между двумя таблицами. Когда приложение для обработки заказов передает заказ в базу данных, база данных обращается к таблице со сведениями о заказах, извлекает сведения о продукции и использует идентификатор заказчика из этой таблицы, чтобы найти сведения об оплате и доставке в таблице с информацией о нем. Затем на складе подбирают нужный продукт, заказчик своевременно получает свой заказ и производит оплату.

Структура реляционных баз данных

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

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

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

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

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

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

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

Преимущества реляционных баз данных

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

Реляционные базы данных появились в 1970-х годах. На сегодняшний день преимущества реляционного подхода сделали его самой распространенной моделью для баз данных в мире.

Целостность данных

Реляционная модель наиболее эффективно поддерживает целостность данных во всех приложениях и копиях (экземплярах) базы данных. Например, когда заказчик кладет деньги на счет с помощью банкомата, а затем проверяет баланс на мобильном телефоне, он ожидает, что поступившие средства сразу же отобразятся на счете. Реляционные базы данных отлично подходят для обеспечения целостности данных в различных экземплярах базы в одно и то же время.

Другие типы баз данных не могут одновременно поддерживать целостность больших объемов данных. Некоторые современные типы баз данных, такие как NoSQL, обеспечивают только так называемую “окончательную целостность.” Это значит, что, когда выполняется масштабирование данных или несколько пользователей одновременно используют одни и те же данные, необходимо некоторое время на “внесение изменений”. В некоторых случаях окончательная целостность вполне приемлема (например, для обновления позиций в товарном каталоге), однако для критически важной операционной деятельности бизнеса (например, транзакций с использованием корзины) реляционные базы представляют собой фундаментальный стандарт.

Фиксация изменений и атомарность

В реляционных базах данных используются очень детальные и строгие бизнес-правила и политики в отношении фиксации изменений в базе данных (то есть сохранения изменений в данных на постоянной основе). Рассмотрим для примера складскую базу данных, в которой отслеживаются три запчасти, всегда использующиеся в комплекте. Когда одну из них извлекают из товарных запасов, две другие также должны извлекаться. Если одна из трех запчастей недоступна, две другие также не могут быть проданы отдельно, то есть, чтобы в базу данных можно было внести изменения, должны быть доступны все три запчасти. Реляционная база данных не разрешит сохранять изменения, если они не касаются всех трех запчастей. Эту особенность реляционных баз данных называют атомарностью или неразрывностью. Неразрывность необходима для сохранения точности данных в базе и обеспечения соответствия с правилами, нормативными положениями и бизнес-политиками.

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

Транзакции в реляционной базе данных имеют четыре важные характеристики: неразрывность (atomicity), целостность (consistency), изолированность (isolation) и неизменность (durability). Это сочетание получило название ACID.

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

Хранимые процедуры и реляционные базы данных

Доступ к данным включает в себя множество повторяющихся действий. Например, иногда для получения нужного результата простой запрос для получения информации из таблицы необходимо повторить сотню или тысячу раз. Для таких сценариев доступа к базе данных необходимо что-то вроде программного кода. Разработчикам каждый раз писать стандартный код доступа к данным для нового приложения было бы утомительно. К счастью, реляционные базы данных поддерживают хранимые процедуры, представляющие собой блоки кода, к которым можно получить доступ с помощью обычного вызова со стороны кода приложения. Например, одну и ту же хранимую процедуру можно использовать для последовательной маркировки записей в целях удобства пользователей для различных приложений. Хранимые процедуры также помогают разработчикам убедиться в правильной реализации определенных функций данных в приложении.

Блокировки базы данных и параллельный доступ

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

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

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

Характеристики, на которые следует обратить внимание при выборе реляционной базы данных

Программное обеспечение, которое используется для сохранения, контроля и извлечения данных в базе, а также выполнения к ней запросов, называют системой управления реляционной базой данных (СУРБД). СУРБД обеспечивает интерфейс между пользователями и приложениями и базой данных, а также административные функции для управления хранением данных, их эффективностью и доступом к ним.

При выборе типа базы данных и продуктов на основе реляционных баз данных необходимо учитывать несколько факторов. Выбор СУРБД зависит от потребностей Вашей компании. Задайте себе следующие вопросы.

• Каковы наши требования к точности данных? Будем ли мы использовать бизнес-логику для хранения и обеспечения точности данных? Предъявляются ли к нашим данным более строгие требования в отношении точности (например, если Вы работаете с финансовыми данными и отчетностью)?
• Нужна ли нам масштабируемость? Какими объемами данных требуется управлять и каков прогнозируемый рост этих объемов? Должна ли модель базы данных поддерживать зеркальные копии (как отдельные экземпляры) в целях масштабирования? Если да, сможем ли мы обеспечивать целостность данных в этих экземплярах?
• Насколько важно наличие параллельного доступа? Потребуется ли пользователям и приложениям одновременный доступ к данным? Поддерживает ли ПО базы данных параллельный доступ без ущерба для безопасности?
• Каковы наши потребности в эффективности и надежности баз данных? Требуется ли нам высокоэффективная и надежная система? Каковы требования к скорости выполнения запросов? Какие гарантии дает вендор услуг в соответствии с соглашением об обслуживании (SLA) или на случай незапланированного простоя?

Реляционная база данных будущего: автономная база данных

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

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

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

Источник

Как работают реляционные базы данных (Часть 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(log(n)) остается низкой даже с миллиардами данных.
• Наихудшая сложность — O(n 2 ), где количество операций быстро растет.
• Две другие сложности так же быстро увеличиваются.

Примеры

При небольшом количестве данных разница между O(1) и O(n 2 ) незначительна. Например, предположим, что у вас есть алгоритм, который должен обрабатывать 2000 элементов.

• Алгоритм O (1) обойдется вам в 1 операцию
• Алгоритм O (log (n)) обойдется вам в 7 операций
• Алгоритм O (n) обойдется вам в 2 000 операций
• Алгоритм O (n * log (n)) обойдется вам в 14 000 операций
• Алгоритм O (n 2 ) обойдется вам в 4 000 000 операций

Разница между O(1) и O(n 2 ) кажется большой (4 миллиона операций) но вы потеряете максимум 2 мс, просто время моргнуть глазами. Действительно, современные процессоры могут обрабатывать сотни миллионов операций в секунду. Вот почему производительность и оптимизация не являются проблемой во многих ИТ-проектах.

Как я уже сказал, по-прежнему важно знать эту концепцию при работе с огромным количеством данных. Если на этот раз алгоритм должен обработать 1 000 000 элементов (что не так уж много для базы данных):

• Алгоритм O (1) обойдется вам в 1 операцию
• Алгоритм O (log (n)) обойдется вам в 14 операций
• Алгоритм O (n) обойдется вам в 1 000 000 операций
• Алгоритм O (n * log (n)) обойдется вам в 14 000 000 операций
• Алгоритм O (n2) обойдется вам в 1 000 000 000 000 операций

Я не делал расчетов, но я бы сказал, что с помощью алгоритма O (n2) у вас есть время выпить кофе (даже два!). Если вы добавите еще 0 к объему данных, у вас будет время, чтобы вздремнуть.

Идем глубже

• Поиск в хорошей хеш-таблице находит элемент за O (1).
• Поиск в хорошо сбалансированном дереве дает результат за O (log (n)).
• Поиск в массиве дает результат за O (n).
• Лучшие алгоритмы сортировки имеют сложность O (n * log (n)).
• Плохой алгоритм сортировки имеет сложность O (n 2 ).

Примечание: в следующих частях мы увидим эти алгоритмы и структуры данных.

Есть несколько типов временной сложности алгоритма:

• сценарий среднего случая
• лучший вариант развития событий
• и худший сценарий

Временная сложность часто является наихудшим сценарием.

Я говорил только о временной сложности алгоритма, но сложность также применима для:

• потребления памяти алгоритмом
• потребления дискового ввода / вывода алгоритмом

Конечно, есть сложности хуже, чем n 2 , например:

• n 4 : это ужасно! Некоторые из упомянутых алгоритмов имеют такую сложность.
• 3 n : это еще хуже! Один из алгоритмов, которые мы увидим в середине этой статьи, имеет эту сложность (и он действительно используется во многих базах данных).
• факториал n: вы никогда не получите свои результаты даже с небольшим количеством данных.
• n n : если вы столкнетесь с этой сложностью, вы должны спросить себя, действительно ли это ваша сфера деятельности .

Примечание: я дал вам не реальное определение обозначения «большой О», а просто идею. Вы можете прочитать эту статью в Википедии для реального (асимптотического) определения.

MergeSort (Сортировка слиянием)

Что вы делаете, когда вам нужно отсортировать коллекцию? Что? Вы вызываете функцию sort ()… Ок, хороший ответ… Но для базы данных вы должны понимать, как работает эта функция sort ().

Существует несколько хороших алгоритмов сортировки, поэтому я остановлюсь на самом важном: сортировке слиянием. Возможно, вы сейчас не понимаете, почему сортировка данных полезна, но вы должны будете понять, после части посвященной оптимизации запросов. Более того, понимание сортировки слиянием поможет нам позже понять общую операцию join баз данных, называемую merge join (объединение слиянием).

Merge (слияние)

Как и многие полезные алгоритмы, сортировка слиянием основана на хитрости: объединение 2 отсортированных массивов размера N / 2 в N-элементный отсортированный массив стоит всего N операций. Эта операция называется слиянием.

Давайте посмотрим, что это значит на простом примере:

На этом рисунке видно, что для построения окончательного отсортированного массива из 8 элементов вам нужно всего лишь выполнить итерацию один раз в 2х 4-элементных массивах. Поскольку оба 4-элементных массива уже отсортированы:

• 1) вы сравниваете оба текущих элемента в двух массивах (в начале текущий = первому)
• 2) затем возьмите наименьший, чтобы поместить его в массив из 8 элементов
• 3) и переходите к следующему элементу в массиве, где вы взяли самый маленький элемент
• и повторяйте 1,2,3, пока не дойдете до последнего элемента одного из массивов.
• Затем вы берете остальные элементы другого массива, чтобы поместить их в массив из 8 элементов.

Это работает, потому что оба 4-элементных массива отсортированы, и поэтому вам не нужно «возвращаться» в этих массивах.

Теперь, когда мы поняли этот трюк, вот мой псевдокод для merge:

Сортировка слиянием разбивает задачу на меньшие задачи, а затем находит результаты меньших задач, чтобы получить результат исходной задачи (примечание: этот вид алгоритмов называется разделяй и властвуй). Если вы не понимаете этот алгоритм, не волнуйтесь; я не понял этого в первый раз, когда увидел. Если это может помочь вам, я вижу этот алгоритм как двухфазный алгоритм:

• Фаза деления, где массив делится на меньшие массивы
• Фаза сортировки, где маленькие массивы объединяются (используя объединение), чтобы сформировать больший массив.

Division phase (фаза деления)

На этапе деления массив делится на унитарные массивы за 3 шага. Формальное количество шагов — log(N) (поскольку N=8, log(N) = 3).

Откуда я это знаю?

Я гений! Одним словом — математика. Идея состоит в том, что каждый шаг делит размер исходного массива на 2. Количество шагов — это количество раз, которое вы можете разделить исходный массив на два. Это точное определение логарифма (с основанием 2).

Sorting phase (Фаза сортировки)

На этапе сортировки вы начинаете с унитарных (одноэлементных) массивов. В течение каждого этапа вы применяете несколько операций слияния, и общая стоимость составляет N = 8 операций:

• На первом этапе у вас есть 4 слияния, которые стоят 2 операции каждый
• На втором шаге у вас есть 2 слияния, которые стоят 4 операции каждый
• На третьем шаге у вас есть 1 слияние, которое стоит 8 операций

Поскольку существует log (N) шагов, общая стоимость N * log(N) операций.

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

Почему этот алгоритм такой мощный?

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

Примечание: этот вид алгоритмов называется in-place (сортировка без дополнительной памяти).

• Вы можете изменить его для одновременного использования дискового пространства и небольшого объема памяти без значительных затрат на дисковый ввод/вывод. Идея состоит в том, чтобы загружать в память только те части, которые в данный момент обрабатываются. Это важно, когда вам нужно отсортировать таблицу размером в несколько гигабайт только с буфером памяти объемом 100 мегабайт.

Примечание: этот вид алгоритмов называется внешняя сортировка.

• Вы можете изменить его для запуска на нескольких процессах / потоках / серверах.

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

• Этот алгоритм может превратить свинец в золото (правда!).

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

Массив, Дерево и Хеш-таблица

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

Массив

Двумерный массив — простейшая структура данных. Таблицу можно рассматривать как массив. Например:

Этот 2-мерный массив представляет собой таблицу со строками и столбцами:

• Каждая строка представляет сущность
• Столбцы хранят свойства, описывающие сущность.
• Каждый столбец хранит данные определенного типа (integer, string, date …).

Так удобно хранить и визуализировать данные однако, когда вам нужно найти определенное значение, это не подходит.

Например, если вы хотите найти всех ребят, которые работают в Великобритании, вам нужно будет просмотреть каждую строку, чтобы определить, принадлежит ли эта строка к Великобритании. Это будет стоить вам N операций, где N — количество строк, что неплохо, но может ли быть более быстрый путь? Теперь нам пришло время познакомится с деревьями.

Примечание: большинство современных баз данных предоставляют расширенные массивы для эффективного хранения таблиц: heap-organizedtables и index-organizedtables. Но это не меняет проблему быстрого поиска определенного условия в группе столбцов.

Дерево и индекс базы данных

Двоичное дерево поиска — это двоичное дерево со специальным свойством, ключ в каждом узле должен быть:

• больше, чем все ключи, хранящиеся в левом поддереве
• меньше всех ключей, хранящихся в правом поддереве

Давайте посмотрим, что это значит визуально

Это дерево имеет N = 15 элементов. Допустим, я ищу 208:

• Я начинаю с корня, чей ключ 136. Поскольку 136 208, следовательно, я смотрю на левое поддерево узла 398
• 250>208, следовательно, я смотрю на левое поддерево узла 250
• 200 40, я смотрю на левое поддерево узла 136.
• 80 > 40, следовательно, я смотрю на левое поддерево узла 80
• 40= 40, узел существует. Я извлекаю идентификатор строки внутри узла (этого нет на рисунке) и смотрю в таблице для данного идентификатора строки.
• Знание идентификатора строки, позволяет мне узнать, где именно находятся данные в таблице, и поэтому я могу получить их мгновенно.

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

Возвращаемся к нашей проблеме

Но это очень абстрактно, поэтому давайте вернемся к нашей проблеме. Вместо простого integer, представьте строку, которая представляет страну кого-то в предыдущей таблице. Предположим, у вас есть дерево, которое содержит поле «country» (column 3) таблицы:

• Если вы хотите знать, кто работает в Великобритании
• вы смотрите на дерево, чтобы получить узел, который представляет Великобританию
• внутри «UKnode» вы найдете расположение записей работников в Великобритании.

Этот поиск будет стоить log(N) операций вместо N операций если вы напрямую будете использовать массив. То, что вы только что представили — это был индекс базы данных.

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

B+TreeIndex

Хотя это дерево хорошо работает для получения определенного значения, существует БОЛЬШАЯ проблема, когда вам нужно получить несколько элементов между двумя значениями. Это будет стоить O(N) потому что вам придется посмотреть на каждый узел в дереве и проверить, находится ли он между этими двумя значениями (например, с упорядоченным обходом дерева). Более того, эта операция не удобна для дискового ввода-вывода, так как вам придется читать полное дерево. Нам нужно найти способ эффективно выполнить запрос диапазона. Для решения этой проблемы современные базы данных используют модифицированную версию предыдущего дерева под названием B+Tree. В B+Tree дереве:

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

Как вы можете видеть, здесь узлов больше (в два раза). Действительно, у вас есть дополнительные узлы, «узлы принятия решений», которые помогут вам найти правильный узел (который хранит расположение строк в связанной таблице). Но сложность поиска все еще O(log(N)) (есть только еще один уровень). Большая разница состоит в том, что ноды на нижем уровне связаны с их преемниками.

С этим B+Tree, если вы ищете значения от 40 до 100:

• Вам просто нужно искать 40 (или ближайшее значение после 40, если 40 не существует), как вы делали с предыдущим деревом.
• Затем соберите наследников 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+Tree, иначе временная сложность в O (log (N)) станет O (N).

Другими словами, B+Tree должно быть самоупорядоченным и сбалансированным. К счастью, это возможно с умными операциями удаления и вставки. Но это обходится дорого: вставка и удаление в дереве B+ обходятся в O (log (N)). Вот почему некоторые из вас слышали, что использование слишком большого количества индексов не очень хорошая идея. Действительно, вы замедляете быструю вставку / обновление / удаление строки в таблице, поскольку базе данных необходимо обновить индексы таблицы с помощью дорогостоящей операции O (log (N)) для каждого индекса. Более того, добавление индексов означает большую нагрузку для менеджера транзакций (будет описан в конце статьи).

Для более подробной информации, вы можете посмотреть статью в Википедии о B+Tree. Если вы хотите пример реализации B+Tree в базе данных, посмотрите эту статью и эту статью от ведущего разработчика MySQL. Они оба сосредоточены на том, как InnoDB (движок MySQL) обрабатывает индексы.

Примечание: читатель сказал мне что, из-за низкоуровневых оптимизаций дерево B+ должно быть полностью сбалансировано.

Hashtable (Хеш-таблица)

Наша последняя важная структура данных — это хеш-таблица. Это очень полезно, когда вы хотите быстро искать значения. Более того, понимание хеш-таблицы поможет нам позже понять общую операцию соединения с базой данных, называемую хеш-соединением ( hash join). Эта структура данных также используется базой данных для хранения некоторых внутренних вещей (например, таблица блокировки или буферный пул, мы увидим обе эти концепции позже).

Хеш-таблица — это структура данных, которая быстро находит элемент по его ключу. Для построения хеш-таблицы вам нужно определить:

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

Простой пример

Давайте возьмем наглядный пример:

Эта хеш-таблица имеет 10 сегментов. Поскольку я ленивый, я изобразил только 5 сегментов, но я знаю, что вы умные, поэтому позволю вам представить 5 других самостоятельно. Я использовал хэш-функцию по модулю 10 ключа. Другими словами, сохраняю только последнюю цифру ключа элемента, чтобы найти его сегмент:

• если последняя цифра равна 0, элемент попадает в сегмент 0,
• если последняя цифра равна 1, элемент попадает в сегмент 1,
• если последняя цифра равна 2, элемент попадает в область 2,
• …

Функция сравнения, которую я использовал, это просто равенство между двумя целыми числами.

Допустим, вы хотите получить элемент 78:

• Хеш-таблица вычисляет хеш-код для 78, который равен 8.
• Хеш-таблица смотрит в сегмент 8, и первый элемент, который она находит, это 78.
• Она возвращает вам элемент 78
• Поиск стоит только 2 операции (одна для вычисления значения хеш-функции, а другая для поиска элемента внутри сегмента).

Теперь, допустим, вы хотите получить элемент 59:

• Хеш-таблица вычисляет хеш-код для 59, который равен 9.
• Хеш-таблица ищет в 9 сегменте, первый найденный элемент — это 99. Поскольку 99!=59, элемент 99 не правильный элемент.
• Используя эту же логику, берется второй элемент (9), третий (79), …, последний (29).
• Элемент не найден.
• Поиск стоил 7 операций.

Хорошая хеш-функция

Как видите, в зависимости от значения, которое вы ищете, стоимость не одинакова!

Если я теперь изменю хэш-функцию по модулю 1 000 000 от ключа (то есть, взяв последние 6 цифр), второй поиск будет стоить только 1 операцию, поскольку в сегменте 000059 нет элементов. Реальная задача — найти хорошую хэш-функцию, которая будет создавать сегменты, содержащие очень небольшое количество элементов.

В моем примере найти хорошую хеш-функцию легко. Но это простой пример, найти хорошую хеш-функцию сложнее, когда ключ:

• строка (например — фамилия)
• 2 строки (например — фамилия и имя)
• 2 строки и дата (например — фамилия, имя и дата рождения)
• …

С хорошей хеш-функцией поиск в хеш-таблице обходится в O(1).

Массив vs хеш-таблица

Почему бы не использовать массив?

Хм, хороший вопрос.

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

Для дополнительной информации, вы можете прочитать статью о JavaHashMap, которая является эффективной реализацией хеш-таблицы; вам не нужно понимать Java, чтобы понять концепции, изложенные в этой статье.

Источник