TYPES Trees are represented by two types: entree (enumerated tree) and bitree (bit tree). The corresponding query types are entreequery and bitreequery. tree - The tree type represents a node of a tree as a path from the root to the node. A path is generated using each node's number. Thus, the record by '3.4' indicates the 4th child of the 3rd child of the root. Numbers at each level begin at 1. For the entree tree type, the maximum number of children for each node is 65535. For the bitree tree type, the maximum number of children for each node is determined during compilation and valid values are 8,16,32 (default) and 64. The type is sorted in order of the direct traverse of the tree. treequery - represents a tree node pattern that is used for queries. It's the same type as a tree but with the possibility to use some sort of regular expression. For example, record '1.2|3' indicates the 2nd or 3rd child of the 1st child of the root, and '1.*.4|5' indicates the 4th or 5th child of any child of the 1st child of the root. The examples given above correspond to all descendant nodes. If this is not desirable, it is possible to limit the depth of the pattern matching. For instance: '1.2|3.0' and '1.*.4|5.0', respectively. OPERATIONS The following operations are determined for the tree types: <,>,<=,>=,= and <>. Also, it's possible to match patterns: tree <* treequery treequery >* tree The last two operations return TRUE if the node matches the treequery pattern. Operation tree @> tree returns TRUE if the left argument is the ancestor of the right or equal to it. The respective operation tree <@ tree returns TRUE if the right argument is the ancestor of the left or equal to it (the left argument is the descendant of the right). FUNCTIONS entree_level(entree) and bitree_level(bitree) return the level of node. entree_next(entree) and bitree_next(bitree) return the next free node. Example of how to add a node: select entree_next(tid) from dmoz where tid <* '1.2.3.*.0' order by tid desc limit 1; INDICES Type tree supports two types of indices: B-Tree - accelerates operations: <,>,<=,>= and =. Supports all features of regular B-tree - unique indices, merge-join,... GiST - accelerates operations: <,>,<=,>=,=,*>,<*,@> and <@ Arrays of tree The following operations are determined for arrays of tree: tree[] => tree tree <= tree[] tree[] <* treequery treequery *> tree[] The first two operations return true if in the array there is a record equal to another operand of the operations. The last 2 operations return true if there is a record in the array which corresponds to the given pattern. These operations can be accelerated by constructing GiST-indices. NOTICES 1. The following selects are equivalent and return all descendants of node 1.1: select * from treetbl where treefld >= '1.1' and treefld < '1.2'; select * from treetbl where treefld <* '1.1'; select id from dmoz where id <@ '1.1'; 2. Insertion into GiST is several times slower than insertion into B-Tree, while selection performance is at most 1.5 slower. EXAMPLES: create table dmoz ( nodename text, -- the name of node nodepath text, -- path to node intid int, -- the unique identifier id entree ); To obtain all children of the node: select * from dmoz where id <* '1.2.3.*.0'; To obtain all decendants of the node: select * from dmoz where id <* '1.2.3' and id != '1.2.3'; To obtain all children of the node with the calculation of all their descendants: select *, ( select count(*)-1 from dmoz as d where d.id <* entree2query(dmoz.id) ) as descentcount from dmoz where id <* '1.2.3.*.0';