We want something like sqlite, but for Graph Databases!

Most of the existing triple stores and graph databases are very heavyweight services that would be impractical for packaging in a portable daemon in the same way that sqlite works. Maybe we can learn from how sqlite works and do something similar for graph databases?


  • How come these things can be faster than idk like a .json file

  • How are they different architecturally than a traditional SQL server

File Structure#

  • Main file

  • Rollback Journal - stores additional information to restore in case of a crash. Store a copy of the original DB, write changes directly into DB file. COMMIT occurs when rollback is deleted

  • Write-ahead Log - if in WAL mode, append updates to WAL file. COMMIT occurs when writing to WAL file (not to main DB). Multiple transactions can be batched.


Pages are the basic unit of an sqlite file.


  • Each page can be a power of 2 between 512 and 65536

  • All pages are the same size

  • Max 2^32 - 2 pages in a single DB.


Each page has a single type:

  • The lock-byte page

  • A freelist page

    • A freelist trunk page

    • A freelist leaf page

  • A b-tree page

    • A table b-tree interior page

    • A table b-tree leaf page

    • An index b-tree interior page

    • An index b-tree leaf page

  • A payload overflow page

  • A pointer map page


(artifact of windows 95 compatibility)


Linked list of “trunks and leaves” to keep track of unused pages:

  • Trunk pages:

    • Series of 4-byte integers that take up full page

    • First integer is the page number of the next trunk (zero if it’s the last page)

    • Second integer is number of leaf pointers that follow

  • Leaf pages:

    • contain nothing!


(B-tree wiki page)

Two types of b-trees: table and index

  • Table B-Trees:

    • One table b-tree in the db file for each rowid table in the database schema

    • 64-bit signed integer key that refers to the rowid it implements

    • Store all data in leaves (interior pages just point to leaves)

  • Index B-Trees:

    • One index b-tree for each index in the schema

    • Arbitrary keys

    • Store no data.

Two types of b-tree pages:

  • Interior

  • Leaf


Describe freeblocks

Payload Overflow#

Define the “payload” of a cell to be the arbitrary length section of the cell.

  • For an index b-tree, the key is always arbitrary in length and hence the payload is the key.

  • There are no arbitrary length elements in the cells of interior table b-tree pages and so those cells have no payload.

  • Table b-tree leaf pages contain arbitrary length content and so for cells on those pages the payload is the content.

When a payload is bigger than some threshold[1], store it on a linked list of payload overload pages. The first four bytes of each overflow page are a 4-byte big-endian integer indicating the page number of the next page in the chain, or zero for the final page.

Pointer Maps#

Backlinks from child to parent nodes in index trees to assist with vacuuming :)

Each pointermap page provides backlinks for the pages immediately following it.

Each 5-byte ptrmap entry consists of:

  • 1 byte of page type information:

    • 0: A b-tree root page

    • 0: Freelist page

    • prior page or first page: payload overflow page

    • parent page: non-root b-tree page

  • 4 byte big-endian page number







How does writing and querying an sqlite file actually work???

All reads from and writes to the main database file happen at a page boundary.

All writes are an integer number of pages in size.

Most reads are also an integer number of pages in size, except opening the database which reads the header (first 100 bytes).

See also#