Как написать простой движок базы данных
Мне интересно узнать, как работает механизм базы данных (то есть его внутреннее устройство). Я знаю большинство базовых структур данных, преподаваемых в CS (деревья, хеш-таблицы, списки и т. Д.), А также довольно хорошее понимание теории компиляторов (и реализовал очень простой интерпретатор), но я не понимаю, как это сделать о написании движка базы данных. Я искал учебники по этому предмету и не смог найти ни одного, поэтому я надеюсь, что кто-то другой может указать мне правильное направление. В основном, я хотел бы получить информацию о следующем:
- Как данные хранятся внутри (т. Е. Как представлены таблицы и т. Д.)
- Как движок находит нужные данные (например, запускает запрос SELECT)
- Как данные вставляются быстрым и эффективным способом
И любые другие темы, которые могут иметь отношение к этому. Это не обязательно должна быть база данных на диске - даже база данных в памяти - это хорошо (если это проще), потому что я просто хочу изучить принципы, стоящие за ней.
Большое спасибо за вашу помощь.
9 ответов
Если вы хорошо читаете код, изучение SQLite научит вас всему, что нужно для проектирования баз данных. Он маленький, поэтому легче обернуть голову. Но это также профессионально написано.
Ответ на этот вопрос огромен. ожидаю, что докторская диссертация ответит на все 100%;) но мы можем думать о проблемах одна за другой:
Как хранить данные внутри: у вас должен быть файл данных, содержащий объекты вашей базы данных и механизм кэширования, чтобы загрузить данные в фокусе и некоторые данные вокруг них в ОЗУ, если у вас есть таблица, с некоторыми данными, мы бы создали формат данных преобразовать эту таблицу в двоичный файл, согласовав определение разделителя столбца и разделителя строк и убедившись, что такой шаблон разделителя никогда не используется в ваших данных. например, если вы выбрали <*>, например, для разделения столбцов, вы должны проверить данные, которые вы помещаете в эту таблицу, чтобы не содержать этот шаблон. Вы также можете использовать заголовок строки и заголовок столбца, указав размер строки и некоторый внутренний индексный номер, чтобы ускорить поиск, и в начале каждого столбца иметь длину этого столбца, такую как "Адам", 1, 11.1, "123 ABC Street POBox 456" вы можете использовать его как<& RowHeader, 1><& Col1, CHR, 4>Adam<& Col2, num, 1,0>1<& Col3, Num, 2,1>111<& Col4, CHR, 24>123 ABC Street POBox 456<& RowTrailer>
Как быстро найти элементы Попробуйте использовать хеширование и индексирование, чтобы указать на данные, сохраненные и кэшированные на основе различных критериев, используя тот же пример, что и выше, вы можете отсортировать значение первого столбца и сохранить его в отдельном объекте, указывая на идентификатор строки элементов, отсортированных по алфавиту., и так далее
Как ускорить вставку данных, которые я знаю из Oracle, заключается в том, что они вставляют данные во временное место, как в ОЗУ, так и на диск, и выполняют периодическое обслуживание, ядро базы данных все время оптимизирует свою структуру, но в то же время мы этого не делаем хотите потерять данные в случае сбоя питания чего-то подобного. поэтому постарайтесь хранить данные во временном месте без сортировки, добавить исходное хранилище, а затем, когда система будет свободна, прибегнуть к индексам и очистить временную область, когда это будет сделано.
удачи, отличный проект.
Есть книги по этой теме, которые можно начать с " Систем баз данных: полная книга " Гарсии-Молины, Уллмана и Видома.
SQLite упоминался ранее, но я хочу добавить кое-что.
Я лично многому научился, изучая SQlite. Интересно то, что я не пошел к исходному коду (хотя я только кратко посмотрел). Я многому научился, читая технический материал и особенно глядя на внутренние команды, которые он генерирует. Он имеет собственный интерпретатор на основе стека, и вы можете прочитать P-код, который он генерирует внутри, просто используя объяснение. Таким образом, вы можете увидеть, как различные конструкции транслируются в низкоуровневый движок (это удивительно просто - но в этом и секрет его стабильности и эффективности).
Я бы предложил сосредоточиться на www.sqlite.org
Это недавно, маленький (исходный код 1MB), с открытым исходным кодом (так что вы можете понять это для себя)...
Были написаны книги о том, как это реализовано:
http://www.sqlite.org/books.html
Он работает на различных операционных системах как для настольных компьютеров, так и для мобильных телефонов, поэтому экспериментировать легко и узнавать о нем будет полезно прямо сейчас и в будущем.
Здесь даже есть приличное сообщество: https://stackru.com/questions/tagged/sqlite
Хорошо, я нашел сайт, на котором есть некоторая информация о SQL и его реализации - немного сложно сослаться на страницу со списком всех учебных пособий, поэтому я буду связывать их по одному:
Может быть, вы можете узнать из HSQLDB. Я думаю, что они предлагают небольшую и простую базу данных для обучения. Вы можете посмотреть на коды, так как это с открытым исходным кодом.
Если MySQL вас интересует, я бы также предложил эту вики-страницу, на которой есть некоторая информация о том, как работает MySQL. Кроме того, вы можете взглянуть на Понимание MySQL Internals.
Вы можете также рассмотреть возможность использования не-SQL-интерфейса для вашего компонента Database Engine. Пожалуйста, посмотрите на Apache CouchDB. Это то, что вы бы назвали, ориентированная на документы система баз данных.
Удачи!
Я не уверен, будет ли это соответствовать вашим требованиям, но я реализовал простую файлово-ориентированную базу данных с поддержкой простых (SELECT, INSERT , UPDATE) используя Perl.
Я сохранил каждую таблицу как файл на диске и записи с четко определенным шаблоном и управлял данными, используя встроенные инструменты linux, такие как awk и sed. для повышения эффективности часто используемые данные кэшируются.