Как работают базы данных внутри?

Question

Я работаю с базами данных в течение последних нескольких лет, и я хотел бы подумать, что я получил достаточную компетентность в их использовании. Однако недавно я читал о Joel's Law of Leaky Abstractions, и я понял, что хотя я могу написать запрос, чтобы получить практически все, что я хочу из базы данных, я понятия не имею, как база данных фактически интерпретирует запрос. Кто-нибудь знает какие-либо хорошие статьи или книги, которые объясняют, как базы данных работают внутри страны?

Некоторых конкретных вещей, я интересуюсь являются:

• Что база данных действительно сделать, чтобы выяснить, что соответствует оператору выбора?
• Как база данных интерпретирует соединение по-разному с запросом несколькими операциями «where key1 = key2»?
• Как база данных хранит всю свою память?
• Как хранятся индексы?

Answer 1

Что база данных на самом деле сделать, чтобы выяснить, что соответствует выберите заявление?

Чтобы быть грубым, это вопрос грубой силы. Просто он читает каждую запись кандидата в базе данных и сопоставляет выражение с полями. Итак, если у вас есть «выбрать * из таблицы, где name = 'fred», она буквально пробегает каждую запись, захватывает поле «имя» и сравнивает ее с «fred».

Теперь, если поле «table.name» индексируется, база данных (вероятно, но не обязательно) сначала использует индекс, чтобы найти записи кандидатов для применения фактического фильтра.

Это уменьшает количество записей кандидатов для применения выражения, иначе оно просто сделает то, что мы называем «сканирование таблицы», т. Е. Читаем каждую строку.

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

Как база данных интерпретирует объединение по-разному на запрос с несколькими «где key1 = key2» заявления?

Ну, соединение используется для создания новой «псевдо-таблицы», на которой применяется фильтр. Таким образом, у вас есть критерии фильтра и критерии соединения. Критерии присоединения используются для создания этой «псевдо-таблицы», а затем фильтр применяется к этому. Теперь, когда интерпретируется соединение, это опять та же проблема, что и сравнение фильтров - грубая сила, и индекс читает, чтобы построить подмножество для «псевдо таблицы».

Как хранить всю свою память ?

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

Как хранятся индексы?

B + Деревья обычно, вы должны посмотреть его. Это простая техника, которая существует уже много лет. Это выгодно для большинства сбалансированных деревьев: последовательный доступ к узлам, плюс все узлы листа связаны, поэтому вы можете легко переходить от узла к узлу в порядке очереди. Таким образом, с индексом строки можно считать «отсортированными» для определенных полей в базе данных, и база данных может использовать эту информацию для оптимизации. Это отличается от, скажем, использованием хеш-таблицы для индекса, что позволяет быстро перейти к определенной записи. В B-Tree вы можете быстро получить не только определенную запись, но и точку в отсортированном списке.

Фактическая механика хранения и индексирования строк в базе данных действительно довольно проста и понятна. Игра управляет буферами и преобразует SQL в эффективные пути запросов, чтобы использовать эти основные идиомы хранения.

После этого, в дополнение к идиоме хранения, есть целая многопользовательская система, блокировка, протоколирование и транзакция.

Answer 2

• Что база данных действительно сделать, чтобы выяснить, что соответствует оператор выбора?

  БД используются индексы (см.ниже)

• Как база данных интерпретирует объединение по-разному для запроса с несколькими «где key1 = key2» заявления? Присоединение Операции могут быть переведены на двоичные операции дерева путем слияния деревьев.

• Каким образом база данных хранит всю память?

  memorymapped файлы для быстрого доступа к их данным

• Как индексы хранятся?

  Внутренние БД работают с B-Trees для индексирования.

Это должно быть объяснено более подробно на википедии ..

http://en.wikipedia.org/wiki/B-tree

http://en.wikipedia.org/wiki/Database

Answer 3

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

Я сделал три попытки написать объяснение, но это действительно слишком большая тема. Проверьте статью Хеллерстайн (тот, что на сервере беркелей, с которым связан Саиф), а затем спросите о специфике.

Следует отметить, что в любой СУБД реализована только подмножество «известных хороших идей». Например, SQLite даже не делает хеш-соединения, он имеет только вложенные циклы (ack !!). Но тогда это легко встраиваемые dbms, и он делает свою работу очень хорошо, поэтому есть что сказать об отсутствии сложности.

Изучение того, как СУБД собирает статистические данные и как они используют их для построения планов запросов, а также изучение того, как читать планы запросов, в первую очередь, является неоценимым навыком - если вам нужно выбрать одну «базу данных» внутренности ", чтобы узнать, узнать это. Это сделает мир различий (и вы никогда не будете случайно писать картезианский продукт снова ... ;-)).

Answer 4

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

Answer 5

Если вы хотите узнать более подробно, я бы рекомендовал получить источники sqlite и посмотреть, как он это делает. Он завершен, хотя и не в масштабе крупных открытых источников и коммерческих баз данных. Если вы хотите узнать более подробно, я рекомендую The Definitive Guide to SQLite, который является не только отличным объяснением sqlite, но и одной из самых читаемых технических книг, которые я знаю. На стороне MySQL вы могли бы узнать от MySQL Performance Blog, а также от книги O'Reilly High Performance MySQL (V2), автором которой является один из авторов.