NYCPHP Meetup

[csnyder]

On 10/28/05, George Schlossnagle <george at omniti.com> wrote:

> In my experience, the only place I've implemented this was where I
> could do batched inserts via rebuilds.  Why inserting individual
> nodes can be a pain, it's on the same order of complexity as
> rebuilding the entire table.
>

This is only partly true -- you can queue new nodes and batch-insert
them, provided they are all going to the same place. But if the append
points are scattered throughout the tree, batching doesn't give you
anything.

"Walking the tree" to rebuild the table takes much much longer than
simply appending a node.

One strategy I considered was inserting two or more "unattached" nodes
on any append, to provide spare capacity in the tree with no extra
cost (adding 4 to each left and right value is the same as adding 2).
But this just seems like madness since it will inflate the tree to
twice its optimal size, and end up compounding the problem.

Grrrrr.

Creating a loosely-connected hierarchy, some means of distributing the
tree across multiple tables (or even multiple databases) seems like
the only sustainable solution. Hans Z. has been musing about
multi-dimensional NSM, whereas I keep coming back to namespaces. But I
still don't know what either of those solutions really looks like...

--
Chris Snyder
http://chxo.com/