Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

B-Trees: More Than I Thought I'd Want to Know (2021)

benjamincongdon.me

Post reply on HN
Print view View original

11–17 of 17 posts

Re: B-Trees: More Than I Thought I'd Want to Know (2021)

#11

Post by iambvk »

prpl wrote: post #2

Missing b-link trees/concurrency/locking, but maybe that really is more than you want to know

I am working on implement on-disk B+Tree for the last few months. Man, keeping the on-disk state consistent with proper locking is a real challenge -- specially when we want to avoid IO-holding-mutex. And forward/backward iterators make me doubt the correctness.

All this with just fixed size keys/values. I am yet to start on variable sized keys and values, but I already want to give up on my initial performance targets.

Re: B-Trees: More Than I Thought I'd Want to Know (2021)

#12

Post by hiimkeks »

> Slotted pages are composed of three components: a header (containing metadata about the page), cells (variable-sized “slots” for data to be stored in), and offset pointers (an array of pointers to those cells). The benefit of this layout is that you can store variable sized data, since the cells can be of variable size, and you don’t need to move that data to logically reorder it. Reordering the positions of the pointers in the pointer array is sufficient. This is inexpensive since the pointers are small, and in a well-known position at the beginning of the page. In other words, as long as the offset pointers are ordered in key-sorted order, it doesn’t matter where in the actual page the keys are stored.

Does that really make a difference if we have to re-write the entire tree node anyway, even if it's just for reordering the pointers (because node == page)?

Re: B-Trees: More Than I Thought I'd Want to Know (2021)

#14

Post by tomnipotent »

hiimkeks wrote: post #12

> Slotted pages are composed of three components: a header (containing metadata about the page), cells (variable-sized “slots” for data to be stored in), and offset pointers (an array of pointers to those cells). The benefit of this layout is that you can store variable sized data, since the cells can be of variable size, and you don’t need to move that data to logically reorder it. Reordering the positions of the po…

> Does that really make a difference if we have to re-write the entire tree node

The I/O write is a fixed cost, but sorting the data to match the pointers would require additional CPU cycles for an outcome that wouldn't really make a difference for subsequent operations.

Re: B-Trees: More Than I Thought I'd Want to Know (2021)

#15

Post by dibyendu »

I implemented a concurrent recoverable B-link Tree some years ago based on research publication by Ibrahim Jaluta. Some details are here:

https://simpledbm.readthedocs.io/en/latest/developerguide.ht...

Implementation is here: https://github.com/dibyendumajumdar/simpledbm

Re: B-Trees: More Than I Thought I'd Want to Know (2021)

#16

Post by nayuki »

QuadrupleA wrote: post #13

I made a SQLite disk-page explorer a little while ago, helped me understand B-trees a lot better: https://github.com/QuadrupleA/sqlite-page-explorer

I understood B-trees for their own sake since 2017 ( https://www.nayuki.io/page/btree-set ), not motivated by SQLite.

But relevant to what you shared, I wrote some tools in 2023 to parse SQLite files in TypeScript, right in the web browser: https://www.nayuki.io/page/sqlite-database-file-visualizatio...

Post reply on HN