Binary links Re: Question Backlog for Valentina mailing list.

[Ed Kleban]

On 11/16/05 12:45 PM, "Ruslan Zasukhin" <sunshine at public.kherson.ua> wrote:

> On 11/16/05 9:16 AM, "Ed Kleban" <Ed at Kleban.com> wrote:
> 
>>>> But I just now read all the doc in both the Kernel and RB Reference about
>>>> Binary Links and decided I don't have a clue about what they do or how to
>>>> use 'em.
>>> 
>>> They do effectively the same as you do in Relational model with help of
>>> third Table to establish M:M link.
>>> 
>>> What do this table? It just remember pairs  (id1, id2)
>>> 
>>> BinaryLink do the same, but use RecIDs and it is NOT a table.
>>> It is more effective structure.
>> 
>> Hmm, more effective than a table.  Meaning not a linear list of pairs, or
>> meaning not a list that's the same length as one of the two related tables.
>> The former I guess.  Hmm... Well, you could certainly make it more efficient
>> by keeping two separate indexed lists so you could do a binary search in
>> either direction.
> 
> right
> 
>> And you could make it more efficient with an indexed list
>> that pointed to a "bucket" with a block of corresponding related entries so
>> that when doing a binary search you didn't have the overhead of duplicates,
>> and once you did the seach you had a linear list of corresponding records.
>> Yeah, that's probably how I'd do it... if I could avoid the temptation of
>> hashing the indexes to avoid the log2N cost of the binary search for large
>> sets of links.
> 
> Valentina have about 5 different kinds of indexes it seems.
> 
> And non of them is Btree or Hash.
> All is something else

Yeah, well, you're making a convert out of me on that approach pretty
quickly.  I've just finished a first pass at re-diagramming the database I'm
designing using Binary Links instead of ObjectPtr fields.  It's amazing!

One question that has come up, is that if I want to associate some type of a
typeCode that is a small byte constant that identifies the type of an item,
and I need to access that typeCode all the time for items to do select case
statements and such, and I also want to keep an anciallary table with
additional information about that typeCode, then should I:

1) Both create a Binary link between item and their typeInfo records, where
the recID is inherently a representation for the typeCd, and then
additionally allocate a byte TypeCode field in the item records, under the
theory that I can grab the typeCode very fast most of the time, and then do
an indexed lookup by record ID when I occasionally need the extra type
info...

or

2) Punt the darn typeCode byte in the item record because binary links are
so blazingly fast in the many to 1 direction that that having a typeCode
byte would be no faster and just make for messy double book keeping.

or 

3) Right idea, but if you really want the blazingly fast connect from the
typeCode in the item record to the typeInfo record then use a full Ulong for
the typeCode as an OffsetPtr because Valentina will optimize accesses and be
more efficient using the ObjectPtr than converting from a byte index.




> :-)