Search code examples
databasesqliteb-tree

What is the degree of B-Tree in Sqlite?


What is the maximum number of nodes that each node can have in the B-Tree used in Sqlite? Are those numbers similar to other relational databases?


Solution

  • SQLite uses a fixed page size that defaults to 4096 bytes but which can be set to any power of two between 512 and 65536. There is some fixed overhead per page (8 bytes for leaf pages, 12 bytes for interior pages), some fixed overhead per slot (2 bytes in the indirection vector plus varying amounts depending on page type and whether it's an index or a table) and the keys/records occupy varying amounts of space depending on their structure and content, and whether stuff has been spilled into overflow pages. In that regard the layout of B-tree pages in SQLite is similar to the layouts used in many other relational databases, and it achieves similar levels of occupancy.

    What sets SQLite a bit apart is the heavy use of variants, variable-length integers (varint) and the quasi universal row overflow capability. This introduces so many variables that a size/occupancy estimation is nowhere near as straightforward, accurate and reliable as for, say, classic B-tree tables in MS SQL Server. It is certainly beyond my limited capabilities, unfortunately...

    You can read the whole story in the section B-tree Pages of the Database file format documentation at sqlite.org.

    P.S.: please heed Shawn's comment regarding the sqlite3 analyser program. I told you at length why it is difficult to say for sure whether God exists, and Shawn points you at a program that simply goes and gives you His bleedin' phone number. ;-)