Re: Possible Glib BTree substitute

[Havoc Pennington <hp redhat com>]

Havoc Pennington <hp@redhat.com> writes:
>    Finding the list of tags involves walking up the tree from a leaf, 
>    and at each parent node adding up the number of tag toggles below 
>    that node (if you look at the code, in frootkxtbtree.c, inc_count()
>    is the function that shows up most in the profiling). Basically 
>    this operation is O(n) in the number of parent nodes a line has.
>    So, this will be faster if the skip list is shallower than the
>    tree.
> 

Argh, I screwed this up. It involves walking over the nodes _before_
the line in question, just like any other search (by line number, char
count, etc.) Duh.

So performance depends on the number of nodes you have to walk over in
order to arrive at the target node, i.e. performance should be
proportional to the speed of lookup by line or char number or any
other index.

Havoc