March 20, 2009

Miscellaneous Perverse Tree Tricks

Unless you're Google, SQL-based relational databases are the de facto standard for storing web application data. Trouble is, MySQL et al. are great at storing relations - lists and sets, essentially - and are absolutely horrible for everything else, right?
Well, not quite. Tree structures are easily and efficiently stored using modified preorder traversal, which relies on nested intervals. This alone is enough to tackle many problems, like ACL-style permissions. I've seen the adjacency list method in use - if you like scalability, don't do it.

(For the truly masochistic: you can even pull off a decent directed acyclic graph implementation by computing the transitive closure.)

No comments:

Post a Comment