News for hackers. Stuff that matters.
Re:The ancient world before computers had stacks or heaps by Retr0id on Wednesday April 03, 2024 @11:40AM (#39918898)
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.

Re:The ancient world before computers had stacks or heaps by felixge on Wednesday April 03, 2024 @12:19PM (#39919361)
This sounds like it was copied from PostreSQL which SQLite cites as a strong source of inspiration.
Re:The ancient world before computers had stacks or heaps by hiAndrewQuinn on Wednesday April 03, 2024 @12:05PM (#39919204)
We 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!
Re:The ancient world before computers had stacks or heaps by andrewshadura on Wednesday April 03, 2024 @06:26PM (#39924066)
FYI, he's D. R. Hipp, not Dr. Hipp.
Re:The ancient world before computers had stacks or heaps by jcgrillo on Wednesday April 03, 2024 @06:37PM (#39924198)
More like Dr. D. R. Hipp, actually.
Re:The ancient world before computers had stacks or heaps by tomcam on Wednesday April 03, 2024 @10:27PM (#39925909)
Hilarious and true
Re:The ancient world before computers had stacks or heaps by jeffrallen on Thursday April 04, 2024 @05:30PM (#39936008)
Great rapper name.
Re:The ancient world before computers had stacks or heaps by tanelpoder on Wednesday April 03, 2024 @03:44PM (#39922125)
Oracle does this as well and I suspect many other row-major RDBMS storage engines do too.
Re:The ancient world before computers had stacks or heaps by suncherta on Wednesday April 03, 2024 @05:37PM (#39923527)
As 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.