No subject


Fri Feb 17 02:32:51 UTC 2012


   Theorem 5: A search in a perfectly balanced ternary search tree
   representing n k-vectors requires at most lg n + k scalar
   comparisons.

In a ternary search tree, the scalar comparison is much
more costly than a tight strcmp loop.

---------------------------------------------------------

Sizing and resizing will still be an issue. The order of
entries in the active file must be preserved so that it
can be MMAPed, and the active file is not necessarily sorted.
So the "sorting" that you get from a ternary search tree
isn't actually useful.

A rmgroup is still going to "hurt."  (But I think TODO already
has a note about that, or do I remember wrong?)

---------------------------------------------------------

Again, I don't object to that note in TODO, but it sure isn't
clear to me that ternary search trees are "the" solution to
use.

Forrest








More information about the inn-workers mailing list