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 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.
