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

# Re: hash & balanced trees

- Date: Mon, 7 Jul 1997 13:59:47 -0400 (EDT)
- From:
- Content-Type: TEXT/PLAIN; charset=US-ASCII
- In-Reply-To: <199707071629.LAA26965@eli.wariat.org>

    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
               allowed.

               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 -(+,-,-(+,-)),
               etc.

               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 ?

    l8r,
    v

References:

- Re: hash & balanced trees

- From: "Robert J. Brown" <rj@eli.wariat.org>

- Prev by Subject: Re: hash & balanced trees
- Next by Subject: RE: hash & balanced trees
- Prev by thread: Re: hash & balanced trees
- Next by thread: re:hash & balanced trees
- Index(es):
  - Subject
  - Thread

Home | Subject Index | Thread Index