GOLF(2gg)

📦 version 601.4.41, in ubuntu questing

💖 GOLF(2gg) — the new-tree page, but make it cute 💖

okay bestie, welcome to the GOLF(2gg) manual, section 2gg, and today's main character is new-tree. sit down, grab a strawberry 🍓, we're building a tree.

✨ NAME ✨

new-tree — literally the tree creation girlie 🌳 (category: (tree))

🎯 PURPOSE 🎯

spawning a brand new tree structure so your key searching goes fast fast ✨

🛠 SYNTAX 🛠

new-tree <tree> \
    [ key-as "positive integer" ] \
    [ unsorted ]
    [ process-scope ]
no cap, that backslash situation is exactly how it's written. we don't question the ancestors 💅

💅 DESCRIPTION 💅

new-tree initializes a new <tree>. that's it. that's the job. and she slays at it.

an tree is a hierarchical balanced binary tree structure that lets you access data in O(log N) time, which means at most approximately "log N" comparisons are needed to find a key in it. so like, to find a key among 1,000,000 keys it would take at most about 20 comparisons. twenty. that's the whole vibe. 🦋

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. not me getting emotional over constant time 😭. 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. it's giving chaos but make it organized.

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

🔑 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 — no duplicates allowed, this is a monogamy situation 🙈. 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 a certain number of times in order to find a specific key. keys are compared using C's strcmp() function, meaning using ASCII lexicographic order. periodt.

🔢 NUMBER KEYS 🔢

the "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. shorter queen, faster queen 👑

🌀 UNSORTED TREE 🌀

if the "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 the "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> will keep its nodes between all requests served by the same process; otherwise <tree> is purged at the end of request. gone. evaporated. poof 🧚

🌸 EXAMPLES 🌸

create a new tree:

new-tree my_tree

iconic. she's born. 🎀

👀 SEE ALSO 👀

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

and that's the whole page bestie!! 💜 this was the GOLF(2gg) manual, dated $DATE at version $VERSION — tysm for reading, go build a tree, and remember: range searches are a love language 🫶✨

📦 where this page comes from