From: Brian Candler <B.Candler@...>
Date: 2004-10-08T20:59:46+09:00
Subject: Re: [ANN] ndb Object-Relational Mapper

On Fri, Oct 08, 2004 at 06:24:44PM +0900, George Moschovitis wrote:
> >Having a hierarchy can be useful too, e.g. for access control, where a
> >user can only "see" objects which are below them in the tree. And XML is
> >still useful as an export/import tool, even if most people on this list use
> >YAML anyway :-)
> 
> well n/Db fully supports a hierarchy. Have a look at the Child and 
> ParentClass and at DbConnection#children etc.

Yep. The trouble with just having a child/parent link is that it's very
inefficient to do a search which is limited to all nodes within a subtree,
and this is the one vaguely clever bit of what I've implemented. Each node
has a 'path' attribute stored in a compacted form. It has the property that

   select * from elements where path like 'ABC%' order by path;

will give you all the elements under node ABC, *and* in the correct order to
spool them out to XML (each parent preceeds its children). It's very easy to
perform searches which are limited to any arbitary subtree.

The path is constructed using these rules:

* root node has path ""
* a child has a path constructed of its parent's path plus a child ID
* the child ID counts from 0, and is encoded into a variable-length string
  using base64, using symbols 0-9 and A-V for numbers 0-31.

    x          0 to 31
    Wxx        32 to 2^10-1
    Xxxxx      2^10 to 2^20-1
    Yxxxxxx    2^20 to 2^30-1
    Zxxxxxxxx  2^30 to 2^40-1

Such paths can be easily decomposed by inspection, e.g.

    4AWVUP -> 4 A WVU P -> /4/10/1022/25

and are short enough to be used as a primary key. The variable length
encoding allows for both deep and wide trees with reasonable efficiency.

Anyway, I'll try to stick it up on the web somewhere over the weekend if
anyone wants to play.

Regards,

Brian.