tree encoding limitations

• Garrett Hart <garrett_at_thirdshift.com> wrote:
  > If you have time I have two questions about a post I
  > saw here
  > http://www.thetechone.com/detail-7836043.html where
  > you say:
  >
  > "As of today, I don't think Nested Intervals have
  > any advantage over
  > Materialized Path method."
  >
  > Is this still your belief today?
  >
  > "These 2 methods, however, are still very different
  > from implementational
  > perspective: you have ~4000 characters to store each
  > node for
  > materialized path compared to several dozens bytes
  > for integers."
  >
  > Are you saying materialized path has the advantage
  > here or nested intervals?
  

Let's see, with 4000 bytes one can store paths

1.1.1.1.1.1.1...
2.2.2.2.2.2.2...

up to 2000 levels, right? In another materialized path variation, where the node encoding is padded like this

00001.00001.00001....

the number of levels is still quite big.

Compare it to dyadic binary encoding where

1.1.1.1.1.1.1...

encoding grows like 2^n. Next

2.2.2.2.2.2.2...

is even worse -- 4^n. Finally,

10.10.10....

is growing at alarming rate 2^10*n=1024^n

Farey/Continued Fraction encoding fairs much better:

1.1.1.1.1.1.1...

grows aproximately as 1.6^n, and

2.2.2.2.2.2.2...

grows like 2.41^n. Finally,

10.10.10....

grows almost like 10^n.

RDBMS supporting integers up to 2^32 would be able to represent "skinny" trees in the dyadic encoding up to 32 levels, and "bushy" 10-fold branching trees up to 3 levels only. It would be able to represent "skinny" trees in the Farey encoding up to 47 levels, and "bushy" 10-fold branching trees up to 9 levels! It is fair to conclude that at least in the the bushy tree farey case the bottleneck would be RDBMS storage/performance capabilities (as the number the nodes themselves become quite large), rather than encoding limitation. Received on Mon Mar 28 2005 - 20:49:18 CST