MOO-cows Mailing List Archive

[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]

Re: hash & balanced trees

It is never a bad idea to `over-engineer' when it comes to algorithms 
over data structures.  What seems like an impossible number of elements 
or key density will occur sooner than later.  My disposition is to go 
with a balanced tree approach, with some form of balancing act, a la AVL,
immediately after insertion or deletion of an element.  However as it was 
pointed out previously, one might choose to relax the balancing 
contraints on the tree, at least temporally, until some server idle time.

Whatever mechanism is implemented in the server code (in c where the 
computation complexity is not obscured by some additional layers), the 
issue remains as to what object interface will be exposed at the moo 
level.  A $dictionary object should have the following interface verbs:

/* Adding terms to a b-tree */

    defineb/3,          % +BTree, +Uniqueness, +Order

        /* This predicate can be ignored. It allows you to specify a
           funny sorting order and whether or not duplicates are

           Creates a b-tree named BTree, with the given order, Order.
           The argument BTree must be a ground term. The Order argument
           can be used to specify the sorting order. The default for
           Order is '+', which means sort the entire term in standard
           order. An Order argument such as +(-,+) means "sort the
           principal functor in standard order, the first argument in
           reverse standard order, and the last argument in standard
           order". So you can have order arguments like -(+,-,-(+,-)),

           If Uniqueness = true, then duplicates are not allowed in the
           b-tree. Duplicates are allowed by default.

    recordb/3,          % +Btree, +Key, +Term

        /* Saves the Key and its associated Term under the given Btree */

    replaceb/4,         % +BTree, +Key, +Old, +New

        /* Replaces the term Old saved under Key with the new term New */

/* Reviewing terms in a B-tree */
    retrieveb/3,                % +BTree, ?Key, ?Term

        /* Fetches the Keys and Terms from the Btree according to Order */

    retrieveb_nth/3,            % +BTree, +N, -Key

        /* Fetches the nth Key from the Btree */

    btree_count/2,              % +BTree, -Count

        /* Returns how many elements are in the given Btree */

    % could be implemented: retrieveb_terms/3, betweenb/7, betweenkeysb/4,
    % retrieveb_keys/2, retrieve_terms/2, what_btrees/1

/* Removing terms from a B-tree */

    removeb/2,          % +BTree, +Key

        /* Removes all elements stored under Key in BTree */

    removeb/3,          % +BTree, +Key, +Term

        /* Backtracks. Removes the given Key and Term from Btree. */

    removeallb/1]).     % +BTree

        /* Frees a Btree */

/* The btree predicates.

Here is a summary of what we have.

         | avl trees
insert   | O(log N)
delete   | O(log N)
find     | O(log N)
walk     | O(N)

You might be saying to yourself: but why use avl's, why not 2-3 trees or
something else? As far as I know, there is no algorithm that limits
comparisons as well as avl.  If there is, tell me.  Comparisons are the
most expensive part here.  2-3 trees are optimal in limiting disk
access.  But all our stuff is in memory. 


These are our notes from adding balanced trees to Quintus, (thanks Tom:) 
and proved to be adequate for most tasks.  The outstanding issues were 
related to multiple processes accessing these structures in shared 
memory, where one wanted to allow updates to the tree while a tree walk 
was in progress . . . 

Comments and suggestions ?


Home | Subject Index | Thread Index