Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> tree encoding limitations

tree encoding limitations

From: Vadim Tropashko <vadimtro_invalid_at_yahoo.com>
Date: 28 Mar 2005 18:49:18 -0800
Message-ID: <1112064558.066840.155700@o13g2000cwo.googlegroups.com>

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

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US