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.)
[ Parent
| on HN ]
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.