Shulou(Shulou.com)06/01 Report--

This article mainly shows you the "analysis of the working principle of SQLite database", the content is easy to understand, clear, hope to help you solve your doubts, the following let the editor lead you to study and study the "analysis of the working principle of SQLite database" this article.

SQLite is a small database application for millions of software and devices. SQLite was invented by D.Richard Hipp in August 2000. SQLite is a high-performance, lightweight relational database. If you are willing to learn the internal structure of the database at the coding level, SQLite is the best open source database with highly readable source code and extensive documentation. It becomes a bit difficult to read a later version of SQLite because it contains many new features. In order to understand the basic implementation within the database, you should have a good understanding of the data structure, some knowledge of computing theory, and how the operating system works.

Here, we will look at SQLite version 2.5.0. You can find a simple implementation of the SQLite backend on GitHub. In addition, I found that this repository contains an SQLite 2.5.0 implementation for code reading.

What is a database?

Saving data in a flat file is not efficient to read and store data. The database organizes the data in the appropriate order so that the data is read and written faster. Data can be structured, semi-structured, or unstructured. Databases are mainly used to store structured and semi-structured data. You can mine the database as follows according to the type of data structure to be stored.

Relational database: a common type of database with a table structure. Tables can be related to other tables. The SQL language is used to manipulate data on such databases.

Key-value database: data stored with the associated key. You can retrieve data using a given key. An in-memory database is usually this type of database.

Object database: the data structure is more like an object than a table.

Graph database: Graph database is a collection of nodes and edges, mainly used in data mining and social media applications.

SQLite database architecture

The SQLite database schema is divided into two different parts, named the core and the back end. The core contains interfaces, word splitters, parsers, code generators, and virtual machines that create the execution order for database transactions. The backend includes B-tree, Pager, and OS interfaces to access the file system. Tokenizer, Parser, and the code generator are collectively referred to as compilers, which generate a set of opcodes that run on a virtual machine.

Where do we start?

To understand the architecture of the database, you need to have the following prerequisites.

Good understanding of data structures and algorithms. Especially B-tree, linked list, Hashmaps and other data structures.

Have some understanding of computer architecture. How to read and write disks, paging and caching.

Theoretical computers such as finite automata, context-free grammar and some knowledge of regular expressions.

SQLite architecture cdn-images-1.medium.com/max/1600/1*t5ygkzu6a28fO41ynZ8kgQ.jpeg "> VFS (virtual file system)

File access on Unix and Windows is different from each other. VFS provides a generic API to access files regardless of the type of operating system it is running. The API includes functions to open, read, write, and close files. Here are some of the API used in VFS to read and write data to a file.

/ * Create a connection to file to read write zFilename: file name id: file pointer pReadonly: read or write * / int sqliteOsOpenReadWrite (const char * zFilename, OsFile * id,int * pReadonly); / * Acqure the lock to read file. This function should be called before caling to any file read function. Return 0 if successid: file pointer * / int sqliteOsReadLock (OsFile * id); / * Get the write lock to write into a file. This function should called beforedoing any write operation into the file system.Return 0 if successid: file pointer*/int sqliteOsWriteLock (OsFile * id); / * Move to the given number of offest to read or write into the file*/int sqliteOsSeek (OsFile * id, int offset); / * Read amt bytes from the file with offset pointed by sqliteOsSeek*/int sqliteOsRead (OsFile * id, void * pBuf, int amt); / * Write amt bytes from the pBuf into the file*/int sqliteOsWrite (OsFile * id, const void * pBuf, int amt)

Here, you can start working with files using the sqliteOpenReadWrite function. This function provides you with a pointer to a file that can be used to read or write data. Next, you should acquire the lock before performing any read and write operations. If it is just a read operation, then the read lock should be acquired. Write locks should be acquired for read and write transactions.

You can then read and write by providing the offset of the file to the sqliteOsSeek function to find the location. The offset is the number of bytes from the beginning of the file to the location where the data should be written or read.

Pager

A page is the smallest unit of database transactions on a file system. When the database needs to read data from a file, it requests it as a page. Once a page is loaded into the database engine, it can store the page if it accesses its cache frequently. The number of pages starts with one page. The first page is called the root page. The page size is constant.

/ * Open pager with the given file name*/int sqlitepager_open (Pager* * ppPager,const char * zFilename,int nPage,int nEx); / * Get page specified by the page number*/int sqlitepager_get (Pager* pPager, Pgno pgno, void * * ppPage); / * Start to write data into a page specified in pData*/int sqlitepager_write (void * pData); / * Commit page changes into the file*/int sqlitepager_commit (Pager*); / * Close the connection to the file*/int sqlitepager_close (Pager* pPager); Btree

Btree is a data structure that stores data as a tree based on its value. The simplest form of BTree is a binary tree. The database uses Btree data structures to store indexes to improve database performance. Each node of the Btree contains a list of keys for indexing. You can create a Btree index for each column in the table. Every Btree has a root page, which is the starting point for any Btree search.

To point to a line on Btree, a special pointer called "Cursor" is used. Cursors are used to point to a record specified by the page id and offset, called idx. SQLite stores the database schema on a table called "master_table". Master_table is always stored on the first page of the database.

Learn more about the design of SQLite's B-tree in this article.

/ * Open file connection to a page file name specified by zFileName with nCache size cache*/int sqliteBtreeOpen (const char * zFilename, int mode, int nCache, Btree * * ppBtree) / * Start transaction. This function should called before any btree modification operations*/int sqliteBtreeBeginTrans (Btree* pBt) / * Insert key pKey with nKey byte and value pData with nData byte put into the Btree*/int sqliteBtreeInsert (BtCursor * pCur, const void * pKey, int nKey, const void * pData, int nData) / * Write data into the file*/int sqliteBtreeCommit (Btree* pBt) / * Move cursor to the matching pKey with nKey bytes*/int sqliteBtreeMoveto (BtCursor * pCur, const void * pKey, int nKey, int * pRes) VDBE (Virtual Database engine)

VDBE is a virtual machine that runs a set of operations and is generated by a code generator. All SQL commands, including insert, delete, update, and selection, are converted into a set of opcodes and then run on the virtual machine. Each opcode contains three inputs named p1, p2, and p3. You can think of this input as input to a function.

Below I added a sample execution opcode stack for the following SQL select statement. PC is the instruction ID of the program counter. For me, the most interesting thing about SQLite is that I can view a set of VBDE opcode instructions for a given SQL code by appending the "explain" keyword to the beginning of the SQL query.

Explain select * from foo; personal computer operation code P1P2P3 comments 1 column number 10

Set the number of columns to 12 columns name 00 value set the column name to "value" 3 to open 03 rich

Open the cursor and point it to the third page, the root page of the foo table (p3 is not important

4 verify Cookies460

Make sure the schema has not changed 5 rewind 011

Move the cursor to the first entry 6 pillar 00

Read the data from the Btree load and put it into the stack 7 pillars 00

8ne110

Pop the top two elements from the stack. If they are not equal, jump to instruction P2. Otherwise, proceed to the next instruction.

9 calls back 10

Pop P1 values from the stack and group them into an array. This will be the result line of this SQL expression

10 next 05

Move the cursor to the next record, if the data exits and goes to P2, otherwise go to the next line

11 off 00

Turn off the cursor compiler

Tokenizer, Parser, and Code Generator are collectively referred to as compilers that generate sets of opcodes that run on VBDE. Tokenizer generates a set of tokens by scanning SQL code. It then validates the syntax and generates a parsing tree. The Lemon parser is used to parse a given SQL code through predefined context-free syntax. The code generator converts the parsing tree into a Mini Program written in SQLite opcodes.

The above is all the contents of this article "Analysis of the working principle of SQLite Database". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.