Among all application software, databases may be the most complex.

MySQL's manual has over 3,000 pages, PostgreSQL's manual has over 2,000 pages, and Oracle's manual is even thicker than the two combined.

However, writing your own simplest database is not difficult. There is aposton Reddit that uses only a few hundred words to clearly explain the principle. Below is the content I have organized based on this post.

I. Data Stored in Text Form

The first step is to write the data to be saved into a text file. This text file is your database.

For convenient reading, data must be divided into records, and the length of each record must be fixed. For example, assuming each record is 800 bytes, the starting position of the 5th record is at 3200 bytes.

Most of the time, we don't know which position a record is in; we only know the value of its primary key. In this case, to read data, we can compare records one by one. But this is too inefficient. In practical applications, databases often use the B-tree format to store data.

II. What is a B-tree?

To understand B-trees, we must start with the binary search tree.

A binary search tree is a data structure with very high search efficiency. It has three characteristics.

(1) Each node has at most two subtrees.

(2) The left subtree contains values smaller than the parent node, and the right subtree contains values greater than the parent node.

(3) To find the target value among n nodes, generally only log(n) comparisons are needed.

The binary search tree structure is not suitable for databases because its search efficiency is related to the number of levels. The deeper the data, the more comparisons are needed. In extreme cases, n data items require n comparisons to find the target value. For a database, each level entered requires reading data from the hard disk once. This is very fatal because hard disk read time is far greater than data processing time. The fewer times a database reads from the hard disk, the better.

The B-tree is an improvement on the binary search tree. Its design idea is to concentrate related data as much as possible, so as to read multiple data at once and reduce the number of hard disk operations.

The B-tree also has three characteristics.

(1) A node can hold multiple values. For example, in the figure above, the node with the most values holds 4 values.

(2) Unless the data is already full, no new levels will be added. In other words, a B-tree pursues as few "levels" as possible.

(3) The values in child nodes have a strict size correspondence with the values in the parent node. Generally, if the parent node has a values, then it has a+1 child nodes. For example, in the figure above, the parent node has two values (7 and 16), corresponding to three child nodes: the first child node contains values less than 7, the last child node contains values greater than 16, and the middle child node contains values between 7 and 16.

This data structure is very helpful for reducing the number of hard disk reads. Assuming a node can hold 100 values, a 3-level B-tree can hold 1 million data items. If replaced with a binary search tree, it would require 20 levels! Assuming the operating system reads one node at a time and the root node is kept in memory, then a B-tree searching for a target value among 1 million data items only needs to read the hard disk twice.

III. Indexes

Storing a database in B-tree format only solves the problem of finding data by "primary key". If you want to search other fields, you need to create an index.

An index is a B-tree file using a certain field as the key. Suppose there is an "employee table" containing two fields: employee number (primary key) and name. An index file can be created for names. The file stores names in B-tree format, with each name followed by its position in the database (i.e., which record number). When searching for a name, first find the corresponding record number from the index, then read it from the table.

This index search method is called "Indexed Sequential Access Method", abbreviated as ISAM. It already has multiple implementations (such as the C-ISAM library and the D-ISAM library). As long as you use these code libraries, you can write your own simplest database.

IV. Advanced Features

After implementing the most basic data access (including indexes), some advanced features can also be implemented.

(1) SQL languageIt is the universal operating language for databases, so an SQL parser is needed to parse SQL commands into corresponding ISAM operations.

(2) Database joinIt refers to two tables in a database establishing a connection through a "foreign key". You need to optimize this operation.

(3) Database transactionIt refers to performing a series of database operations in batch. If any step fails, the entire operation fails. Therefore, an "operation log" is needed so that operations can be rolled back on failure.

(4) Backup mechanism: Save a copy of the database.

(5) Remote operation: Allows users to operate the database from different machines via the TCP/IP protocol.

Original source: http://www.ruanyifeng.com/blog/2014/07/database_implementation.html