Nested Intervals Tree Encoding with Continued
Nested Intervals Tree Encoding in SQL
Nested Set Model https://en.wikipedia.org/wiki/Nested_set_model
Recounting the rationals
The Stern-Brocot or Farey Tree http://oeis.org/stern_brocot.html
Infinite Fractions - Numberphile [video] https://www.youtube.com/watch?v=DpwUVExX27E part 2: https://www.youtube.com/watch?v=zv5M9zuZiXo
I updated it in April 2016 to then-current PostgreSQL versions. It was interesting to me to notice not only the improvements in PostgreSQL over those 12 years, but also how my own practices had changed.
Is it reasonable to call this a bidirectional version of Tro05? Skipping the inequality flips and the "lowest index last" by/and encoding snv and sdv (all of them, before they exist, in order) with their parent seems like a very useful improvement to only being able to calc the parents from a sibling and having to count down as the tree grows. Hopefully I didn't butcher that, corrections appreciated.
Predicates 2.5 and 2.6 intuitively are more descriptive and easier to visualize than the Cel04 nested sets 1.1 and 1.2.
numberphile and all of Brady's chans are pure platinum.
> A Novel Method for Representing Hierarchies in a Relational Database Using Bignums and SQLite
Stephen Huntley, Tcl conference 2011.
By essentially skipping every second row of Vadim's, you end up only being able to go about half as deep before you blow BIGINT. And that wasn't so deep to begin with.
I haven't visited this stuff in many years now, but it seems likely that if you were to use the pgmp postgreSQL extension, or something similar that provided arbitrary precision integers/rationals, you would solve the depth limitation.
I'd be really interested to hear about it.
The encoded number is reversible -- the number is encoded in such a way that you can algorithmically calculate/derive each node's parents and ancestors without querying the database or traversing the tree. Possible siblings and children can be calculated the same way (if they exist).
More exotic adaptations might include a form of semantic content-based addressing by mapping the code to coordinates in a metric space. For example, see the similar Calkin-Wilf H-tree layout: https://en.wikipedia.org/wiki/Calkin–Wilf_tree#Definition_an...
Conway games also take values that are fractions but only dyadic numbers (2^k as denominator) https://en.wikipedia.org/wiki/On_Numbers_and_Games