Galaxy_TOC
Bigintreeindb_t1 Encoding Method
WARNING: This is an untested specification, i.e. it lacks implementations.
This document describes the core of the method, how to encode arbitrary precision integers (hereafter:
bigints) to a plain, relational, database in a format, that allows to execute queries
greaterthan and
smallerthan
efficiently.
General scheme:
BigInts are placed to a binary tree. An example of the tree and the rootoriginating vertex
paths:
Bigint Value
as a String

The Number of columns that
list the X,0,1 equals with the
number of levels in the tree minus 1.
In the case of this example: 4  1 = 3 .

73

0

1

X

74

X

X

X

75

1

0

X

76

1

0

1

42

0

X

X

50

0

1

0

34

0

0

X

22

0

0

0

1984

1

X

X



If the
X were to be replaced with
0, then the path
encoding of 34 (0,0,
X) would not differ from 22 (0,0,0). On the other hand, if
prior to the replacement
X > 0, the 0 were to be replaced
with a "digit" that is smaller than the 0, for example,
1, then the 22 would have one
insignificant "negative digit" more than the 34 has.
22==(1)(1)(1) < (1)(1)(0)==34


That encoding has 3 sequential integers as its digits:
(1),0,1.
The traditional ternary system uses slightly different digits, the
0,1,2, but all the rest
of the contemplation stays the same.
{(1),0,1} + 1 = {0,1,2}
73

0

2

1

74

1

1

1

75

2

0

1

76

2

0

2

42

0

1

1

50

0

2

0

34

0

0

1

22

0

0

0

1984

2

1

1



The order of the numbers that are formed from the series of digits that form the path matches that of the
bigints that have been inserted to the tree, regardless of the value of the bigint. As the traditional
relational database engines use decimal systems, the base 3 numbers can be converted to base 10 and stored as
classical C/C++
unsigned int values, which in turn can be queried by using the traditional
SQL.
As the number of levels in the tree, the maximum path length, grows, new C/C++ unsigned int columns can be
added without rewriting any of the previously written data, unless a tree balancing operation is performed.
All of the new
unsigned int columns must be filled with a default value of
1.