The true cost of linked lists

Re:The true cost of linked lists by MontyCarloHall on Monday June 06, 2022 @08:30AM (#31639623)

>turn it into a tree instead of a list

Sounds a lot like “draw the rest of the damn owl.” [0] :-)

DBMSs and file systems use (extremely sophisticated) tree structures under the hood. Not sure that “linked lists are useful if the linking topology is much more complicated than a simple line” is a ringing endorsement of them.

[0] https://pbs.twimg.com/media/Bs13i6LCcAAvwCf.jpg

[ Parent | on HN ]

Re:The true cost of linked lists by marginalia_nu on Monday June 06, 2022 @08:34AM (#31639662)

My point is that this general sketch of a layout with arrays of offset pointers roughly generalizes to something like a B or B+-tree fairly well, and that's a fairly simple data structure. You can absolutely implement a file system with passable performance with either of those tree structures.

( Here's an enjoyably lucid explanation on how to draw such an owl: https://www.youtube.com/watch?v=aZjYr87r1b8 )

[ Parent | on HN ]