#Key Compression
8 messages in this thread
I'm trying to learn about KEY COMPRESSION for index files (b-tree). Is
there any code out there that shows how this can be achieved? Or can
someone recommend a good source? Thanks for the help.
Shmuel,
I've done it, and I talk about it in the upcoming June 1990 issue, but I
didn't include any source code. Here's how I do it.
Keys in a b-tree node are in collated sequence. The first key in a node
is always whole, that is it contains all its ASCII characters. If the next
key repeats any of the leading characters of the first, the repeated
characters are replaced by an escape sequence that specifies how many
characters repeat. This is a form of run-length-encoding. So if you had
these keys:
program, programmed, programmer, progress, progressive
the compressed form would be:
program, <7>med, <9>r, <5>ess, <8>ive
The bracketed digits represent the count which must take a form that
distinguishes them from valid characters. A tree navigator must be serial.
It must start at the first key in order to reconstruct any subsequent
compressed keys.
Al Stevens
shmuel,
Amend that last thought to read, "a node navigator must be serial."
Obviously a b-tree navigator is not serial. Dumb me.
Al
You've already written stuff for june? How do you manage to stay so far
ahead?
–John
June is a special issue, and Jon gave us an unusually early deadline for
that one. I'm working on April now.
Al Stevens
what is the theme of the special issue?
Hypertext.
Talk to someone who has used C_tree or any package that does key
compression. I remember one good abiity was to not store trailing blanks.
–John