SQLite Forum

How is a table with only primary key stored on disk?
Login

How is a table with only primary key stored on disk?

(1) By 6kEs4Majrd on 2020-08-15 22:30:24 [link]

I want to understand how database storage is implemented in sqlite3. In the simplest case, it should be a table with just one primary key field. Could anybody let me know how it is implemented in sqlite3?

https://en.wikipedia.org/wiki/Database_storage_structures

https://jvns.ca/blog/2014/09/27/how-does-sqlite-work-part-1-pages/

The above page says that sqlite3 is based on B tree. But isn't B+ tree better than B tree? Thanks.

https://www.javatpoint.com/b-plus-tree

Any details about the implementation can be explained?

(2) By Stephan Beal (stephan) on 2020-08-15 22:56:20 in reply to 1 [link]

> Any details about the implementation can be explained?

<https://www.sqlite.org/fileformat.html>

(3) By 6kEs4Majrd on 2020-08-16 01:19:47 in reply to 2

It says "An interior page contains K keys together with K+1 pointers to child b-tree pages."

How to make sure the K keys fit in a page? Can keys be strings so that there will be no guarantee that K keys will fit in a page?

Also what are the keys metioned in fileformat.html and the keys in the sense of SQL language? Thanks.

(4) By Keith Medcalf (kmedcalf) on 2020-08-16 02:06:47 in reply to 3 [link]

> How to make sure the K keys fit in a page?

It is called ARITHMETIC.  You know the amount of "space" on a page that can contain data, and you know the size of a key and the size of a pointer.  Therefore the application of rudimentary grade school arithmetic will allow you to compute the maximum number of keys K that can be stored in the available space.

Or was that a "trick question" of some sort?

> Also what are the keys metioned in fileformat.html and the keys in the sense of SQL language? 

```
create table t
(
  c0, c1, c2, c3 ...
  primary key ( key_column_list ),
  unique ( key_column_list )
);
create index i on t ( key_column_list );
```

Is that another trick question?

(5) By 6kEs4Majrd on 2020-08-16 04:22:33 in reply to 4 [link]

> Therefore the application of rudimentary grade school arithmetic will allow you to compute the maximum number of keys K that can be stored in the available space.

So K is not a fixed number? It is not clear from the manual as the manual does not define what "K" is. This looks like a problem that should be fixed in the manual. What if a string to save is too large for a page? Then K is less than 1? What does K<1 means?

> create table t
> (
>  c0, c1, c2, c3 ...
>  primary key ( key_column_list ),
>  unique ( key_column_list )
> );
> create index i on t ( key_column_list );

Are the "keys" mentioned in the manual the same as the "keys" in SQL code? The word "keys" mean differently in different context.

In the above example code, what should be stored in a page? And what are the binary layout in a page?

(6.2) By Keith Medcalf (kmedcalf) on 2020-08-16 15:13:46 edited from 6.1 in reply to 5 [link]

> Are the "keys" mentioned in the manual the same as the "keys" in SQL code? The word "keys" mean differently in different context.

One would expect so, yes.  A "key" is a concatenation of the fields comprising the key (as in the key_column_list) followed by the components of the primary key of the underlying record that are not already included in the key_column_list.  This ensures that every "key" is unique.

In the case of a ROWID table, the primary key is always the ROWID, although there is "syntactic sugar" that permits the use of the term "PRIMARY KEY" as use-one-time-per-declaration alternate spelling for UNIQUE.

(7) By Larry Brasfield (LarryBrasfield) on 2020-08-16 16:55:43 in reply to 5 [link]

Answering just:

> What if a string to save is too large for a page? Then K is less than 1? What does K<1 means?

From [B-tree Pages](https://sqlite.org/fileformat2.html#b_tree_pages): "Large keys on index b-trees are split up into overflow pages so that no single key uses more than one fourth of the available storage space on the page and hence every internal page is able to store at least 4 keys."

Hence, K will never be less than 4 on those pages.  (But see the paragraph beginning with "The number of keys on an interior b-tree page, K,  ...".)

As far as I can see from the clear file format documentation, K will never be less than one.

Regarding:

> It is not clear from the manual as the manual does not define what "K" is. This looks like a problem that should be fixed in the manual. 

Not so.  See above quotation containing "K".  Your problem diagnosis is premature and should be deferred until you have read the documentation much more carefully.

(8.1) Originally by jiana02 with edits by Larry Brasfield (larrybr) on 2024-02-09 06:59:09 from 8.0 in reply to 1 [link]

\[This post was edited by a moderator to remove a sneaky link with an apparent commercial purpose.

This forum is moderated to avoid off-topic posts, abuse, and spam.<br>
This post was merely edited rather than deleted because it appears to
be relevant to the thread topic, generally correct, and likely helpful.
\]

SQLite3 uses a B-tree structure to store data efficiently. Each row in the database corresponds to a leaf node in this tree. B-trees work well for most cases, even though B+ trees might have some advantages for certain queries.

Better for Range Queries
Reduced Height
Separate Leaf Nodes

1. Page Structure: SQLite3 organizes data into fixed-size pages, typically 4096 bytes. Each page can store multiple rows of data. These pages are the basic unit of I/O in SQLite.

2. B-tree Organization: The database content is organized as a B-tree. This means that the data is stored in a hierarchical structure where each level of the tree contains references to other pages or data. The B-tree allows for efficient search, insertion, and deletion operations.

3. Leaf Nodes: In the simplest case with just one primary key field, each leaf node of the B-tree corresponds to a row in the table. The leaf nodes contain the actual data records sorted by the primary key.