Как написать простой движок базы данных [закрыто]

143

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

  • Как данные хранятся внутри (т. Е. Как представлены таблицы и т. Д.)
  • Как механизм находит данные, которые ему нужны (например, выполнить запрос SELECT)
  • Как данные вставляются быстрым и эффективным способом

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

Большое спасибо за вашу помощь.

a_m0d
источник

Ответы:

55

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

http://sqlite.org/

Роберт Харви
источник
2
LOC of sqlite скачать shell.c => 3135, sqlite3.c => 136332, sqlite3ext.h => 447, sqlite3.h => 7097, всего => 147011
Хаджа Минхаджуддин
1
Что, вероятно, примерно так же мало, как вы можете сделать полностью функциональный движок базы данных, используя язык фигурных скобок. SQLite также доступен в C #.
Роберт Харви
1
@Ibrahim Najjar github.com/CsharpDatabase/csharp-sqlite
Роберт Харви
4
Я рекомендую прочитать код SQLite 2.5.0: github.com/davideuler/SQLite-2.5.0-for-code-reading , это ранняя версия SQLite, которую можно скомпилировать и запустить на современном GCC (я тестировал это на MacOS 10.13 и Debian 8)
Дэвид Эйлер
1
cstack.github.io/db_tutorial - хорошая отправная точка.
Ашиш Неги
25

Ответ на этот вопрос огромен. ожидаю, что докторская диссертация ответит на все 100%;) но мы можем думать о проблемах одна за другой:

  • Как хранить данные внутри: у вас должен быть файл данных, содержащий объекты вашей базы данных, и механизм кэширования, чтобы загрузить данные в фокусе и некоторые данные вокруг них в RAM, если у вас есть таблица, с некоторыми данными, мы бы создали формат данных преобразовать эту таблицу в двоичный файл, согласовав определение разделителя столбца и разделителя строк и убедившись, что такой шаблон разделителя никогда не используется в ваших данных. т. е. если вы выбрали <*>, например, для разделения столбцов, вы должны проверить данные, которые вы помещаете в эту таблицу, чтобы не содержать этот шаблон. Вы также можете использовать заголовок строки и заголовок столбца, указав размер строки и некоторый внутренний индексный номер, чтобы ускорить поиск, и в начале каждого столбца иметь длину этого столбца, такую ​​как «Адам», 1, 11.1, "

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

  • Как ускорить вставку данных, которые я знаю из Oracle, заключается в том, что они вставляют данные во временное место как в ОЗУ, так и на диск и периодически выполняют служебную работу, ядро ​​базы данных все время оптимизирует свою структуру, но в то же время мы этого не делаем. хотите потерять данные в случае сбоя питания чего-то подобного. поэтому постарайтесь хранить данные во временном месте без сортировки, добавить исходное хранилище и позже, когда система будет свободна, прибегнуть к индексам и очистить временную область, когда это будет сделано.

удачи, отличный проект.

A.Rashad
источник
11

SQLite упоминался ранее, но я хочу добавить кое-что.

Я лично многому научился, изучая SQlite. Интересно то, что я не пошел к исходному коду (хотя я только кратко посмотрел). Я многому научился, читая технический материал и особенно просматривая внутренние команды, которые он генерирует. Он имеет собственный интерпретатор на основе стека, и вы можете прочитать P-код, который он генерирует внутри, просто используя объяснение. Таким образом, вы можете увидеть, как различные конструкции транслируются в низкоуровневый движок (что удивительно просто - но в этом и секрет его стабильности и эффективности).

Юргена
источник
9

Хорошо, я нашел сайт, на котором есть некоторая информация о SQL и его реализации - немного сложно сослаться на страницу со списком всех учебных пособий, поэтому я буду связывать их по одному:

a_m0d
источник
8

Я бы предложил сосредоточиться на www.sqlite.org

Это недавно, маленький (исходный код 1 МБ), с открытым исходным кодом (так что вы можете понять это для себя) ...

Были написаны книги о том, как это реализовано:

http://www.sqlite.org/books.html

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

Здесь даже есть приличное сообщество: /programming/tagged/sqlite

Майкл Оберт
источник
1
Размер байта для 3.10 теперь составляет почти 7.0 МБ исходного кода. Только немногие из привилегированных людей могли переварить все это за один присест. Тем не менее, это также хорошее место для начала.
Лори Стерн
1
На самом деле. Недавно проведя некоторое время в исходном коде SQLite, чтобы найти ошибку в SQLCipher, это абсолютный кошмар. Жизнь была проще 6 лет назад :-)
Майкл Оберт
Просто быстрый вопрос, так как я пропустил вечеринку. Думаю, было бы намного приятнее (и, возможно, полезно) начать с первой версии? На самом деле я должен сделать это для всех серьезных чтения кода больших проектов?
Николас Хамфри
7

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

nightingale2k1
источник
3

Я не уверен, будет ли это соответствовать вашим требованиям, но я реализовал простую файлово-ориентированную базу данных с поддержкой simple ( SELECT, INSERT , UPDATE) с использованием perl.
Я сохранял каждую таблицу в виде файла на диске и записей с четко определенным шаблоном и манипулировал данными, используя встроенные инструменты linux, такие как awk и sed. для повышения эффективности часто используемые данные кэшируются.

sud03r
источник
1
у вас еще есть код, можете ли вы поделиться ссылкой
GK1
3

Если MySQL вас интересует, я бы также предложил эту вики-страницу , на которой есть некоторая информация о том, как работает MySQL. Кроме того, вы можете взглянуть на Понимание MySQL Internals .

Вы также можете рассмотреть не-SQL-интерфейс для вашего движка базы данных. Пожалуйста, посмотрите на Apache CouchDB . Это то, что вы бы назвали, система баз данных, ориентированная на документы.

Удачи!


источник
И если вы хотите взглянуть на другую базу данных db: sqlserverinternals.com, ее книги по внутренним компонентам SQl-серверов являются первоклассными.
HLGEM