Re:Bryan Cantrill interviews Arthur Whitney (2009)
by geocar on Monday December 02, 2019 @03:15AM
(#21680743)
If you have cycles in your graph, you can build a tree out of a vector of indices, or as a table of parent/child node keys. The former is what John Scholes does[1], and the latter has plenty of common SQL examples.
If you have a non-cyclic tree (e.g. a 256-trie) you can nest it directly: @/ will traverse to nodes, and COW keeps updates from trashing memory too much.
However trees are rarely the best data structure: Binary search on a sorted list can beat b-trees simply because the end of the search will already be in cache, so for a routing table of IP address ranges, I use something like:
[1]: https://youtu.be/DsZdfnlh_d0
If you have a non-cyclic tree (e.g. a 256-trie) you can nest it directly: @/ will traverse to nodes, and COW keeps updates from trashing memory too much.
However trees are rarely the best data structure: Binary search on a sorted list can beat b-trees simply because the end of the search will already be in cache, so for a routing table of IP address ranges, I use something like: