NAME

       new-tree -  (tree)

PURPOSE

       Create new tree structure for fast key searching.

SYNTAX

           new-tree <tree> \
               [ key-as "positive integer" ] \
               [ unsorted ]
               [ process-scope ]

DESCRIPTION

       new-tree initializes a new <tree>.

       An  tree  is  a  hierarchical  balanced  binary  tree structure that allows data access in O(log N) time,
       meaning that at most approximately "log N" comparisons are needed to find a key in it. For instance, that
       would mean to find a key among 1,000,000 keys it would take at most about 20 comparisons. By default  (if
       "unsorted"  is  omitted),  finding  the next lesser or greater key is O(1), meaning iterating in a sorted
       order is nearly instantaneous. A tree is a hybrid tree structure (taking elements from  both  B  and  AVL
       varieties) optimized for in-memory access.

       Information  in  a  tree  can  be inserted, updated or deleted in any order, and accessed in any order as
       well.

       Information in a tree is organized in nodes. Each node has a key and a value. A key is used to search for
       a node in a tree. By default (if "unsorted" is omitted), all nodes in a Golf tree are also  connected  in
       an ordered linked list, allowing for very fast range searches.

       KEYS AND DATA

       A  node in a tree consists of two strings: key and value. There is no limit on the number of nodes in the
       tree, other than available memory. Each key in the tree must be  unique.  Keys  should  be  as  short  as
       possible. Generally, longer keys take longer to search for, insert or delete.

       KEY COMPARISON

       In  order  for  any data tree structure to function, a key comparison must be performed certain number of
       times in order to find a specific key. Keys are compared using C's strcmp() function, meaning using ASCII
       lexicographic order.

       NUMBER KEYS

       "key-as" clause allows one to treat a key as something other than a string when  it  comes  to  ordering.
       When  "positive  integer"  value  is  used,  it will treat a key as a string representation of a positive
       integer number. Such numbers must be zero or positive integers in the 64 bit range,  and  they  must  not
       contain  leading  zeros,  spaces  or other prefix (or suffix) characters. For example, key strings may be
       "0", "123" or "891347". With this clause, sorting these strings according to  their  converted  numerical
       values is much faster than using schemes such as prefixing numbers with zeros or spaces.

       Note that when using "positive integer", you can use numbers in any base (from 2 to 36). In fact, numbers
       expressed in a higher base are generally faster to search for, because they are shorter in length.

       UNSORTED TREE

       If "unsorted" clause is used, <tree> will not be sorted in a double-linked list, which means that finding
       the  next  smaller  or next greater node in repetition (i.e. range search) will be done by using the tree
       structure and not a linked list. This is slower, as each such search is generally done in O(log N)  time.
       Regardless, you can perform range searches in either case (see use-cursor).

       As a rule of thumb, if you do not need range searches or your memory is scarce, use "unsorted" as it will
       save  2  pointers  (i.e. 16 bytes) per key and insertion/deletion will be a bit faster, but be aware that
       range searches will be slower.

       If you need faster range searches or the extra memory is not an issue (it would  be  for  instance  extra
       16MB  per 1,0000,0000 keys), then do not use "unsorted", as your range searches will be faster. Note that
       in this case, insertion and deletion are a bit slower because they need to maintain a double linked list,
       however in general the effect is minimized by faster range searches.

       SCOPE

       A tree is accessible to the current process only, unless "process-scope" clause is used,  in  which  case
       all  requests  served by the process can use it (see do-once for a typical way to create an object with a
       process scope). If "process-scope" is used, then <tree> that will keep its  nodes  between  all  requests
       served by the same process; otherwise <tree> is purged at the end of request.

EXAMPLES

       Create a new tree:

           new-tree my_tree

SEE ALSO

        Tree

       delete-tree get-tree new-tree purge-tree read-tree use-cursor write-tree See all documentation

$DATE                                               $VERSION                                           GOLF(2gg)