News for hackers. Stuff that matters.
Re:How does a B-tree make queries fast? by kevingadd on Saturday December 23, 2023 @07:59PM (#38749973)
I've implemented a high performance btree this way in the past, where each table and each index were separate files (with append-only writes for concurrency). It worked pretty well and wasn't hard to get right, but it had some downsides (in particular, the kernel seemed to struggle with all the paging.)
Re:How does a B-tree make queries fast? by louthy on Saturday December 23, 2023 @08:10PM (#38750056)
> a high performance btree

then …

> the kernel seemed to struggle …

What was the struggle? If it’s performance doesn’t that contradict your earlier statement?

Genuinely interested in what the issue was, not trying to be a pedant

Re:How does a B-tree make queries fast? by tomnipotent on Saturday December 23, 2023 @08:34PM (#38750213)
> What was the struggle?

Performance is always great until you have to hit disk. Not uncommon to rely on mmap at which point your disk access is sub-optimal vs. a hand-tailored buffer manager with strategies to improve disk reads.

Re:How does a B-tree make queries fast? by sschnei8 on Saturday December 23, 2023 @10:18PM (#38750773)
This requires the obligatory https://db.cs.cmu.edu/mmap-cidr2022/
Re:How does a B-tree make queries fast? by mgaunard on Sunday December 24, 2023 @05:51AM (#38752615)
The linux kernel lets you trigger asynchronous writes of the pages as well as synchronous barriers to ensure they've been written.

You don't need to use direct I/O to have fine control.

Re:How does a B-tree make queries fast? by fsckboy on Saturday December 23, 2023 @10:55PM (#38750960)
the purpose of a btree is to optimize when you are hitting the disk, you can't call that the struggle, that's when the btree sings (tho you could consider extensible hashing)
Re:How does a B-tree make queries fast? by kevingadd on Saturday December 23, 2023 @10:57PM (#38750975)
My throughput was significantly higher than sqlite (4x or so, if memory serves), but the kernel spent so much time swapping pages that the mouse cursor stuttered.

A custom page manager would have probably done the trick, but I don't have the technical chops to write one.