3 ms·
SQLite's on-disk format uses a similar array technique for storing the contents of table btree leaf node pages. Within a fixed-size page, there's an array of of
by Retr0id 3y ago
SQLite's on-disk format uses a similar array technique for storing the contents of table btree leaf node pages. Within a fixed-size page, there's an array of offsets growing forwards, and an array of (variable length) row values growing backwards from the end - the latter of which may end up with holes when rows are deleted (iiuc).
It wouldn't surprise me if it was a direct inspiration, since their docs cite TAOCP for the btree structure itself.
- hiAndrewQuinn 3y agoWe know from the Corecursive podcast on the hidden story of SQLite that Dr. Hipp did indeed reference and pull at least one alg straight from Knuth's books, which he had behind his desk. What a different world that must have been!
- andrewshadura 3y agoFYI, he's D. R. Hipp, not Dr. Hipp.
- jcgrillo 3y agoMore like Dr. D. R. Hipp, actually.
- tomcam 3y agoHilarious and true
- jeffrallen 3y agoGreat rapper name.
- deleted 3y ago[deleted]
- felixge 3y agoThis sounds like it was copied from PostreSQL which SQLite cites as a strong source of inspiration.
- tanelpoder 3y agoOracle does this as well and I suspect many other row-major RDBMS storage engines do too.
- suncherta 3y agoAs others have already mentioned this is used in a lot (most?) of databases. It is called "slotted-page". Searching for it gives good discussions/explanations of it.