3 ms·
>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 st
by MontyCarloHall 4y ago
>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 https://pbs.twimg.com/media/Bs13i6LCcAAvwCf.jpg
- marginalia_nu 4y agoMy 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 https://www.youtube.com/watch?v=aZjYr87r1b8 )