Re: "index" efficiency... any help or ideas?

From: Alex McDonald (alex_mcd_at_btopenworld.com)
Date: 12/15/03 

Date: Mon, 15 Dec 2003 20:13:05 +0000 (UTC)

"Bx. C" <null@the.void> wrote in message
news:bEkDb.5$Xd6.1@bignews6.bellsouth.net...
===snipped

Do a search on "b trees" in google. Some of the papers I found might help
you refine your algorithm. B trees are powerful data structures; of some
significance to your problem is a technique called "front end key
compression" that doesn't require the storing of the entire key in each of
the subtrees. In other words, if I got to this part of the tree due to my
search key starting ABCDEF... then I don't need to store ABCDEF in the
strings in this part of the tree; all the entries in this subtree start with
ABCDEF. I _think_ this may be what you're trying to do. They're also pretty
good at allowing insertions/deletions without becoming very unbalanced.
Again, they're more suited to disk file systems. Grey bearded geek note; the
IBM VSAM access method (file system) uses B trees for its indices. 

-- 
Regards
Alex McDonald

Relevant Pages

  • Re: Create all binary trees of height n
    ... what all-bts should return. ... Now how do we find the list of all trees of height, say, 100? ... * both of its left and right subtrees are of height = 99. ... (combine-trees '(a b) ') should return the following ...
    (comp.lang.scheme)
  • Re: Create all binary trees of height n
    ... Now how do we find the list of all trees of height, say, 100? ... * both of its left and right subtrees are of height = 99. ... (all-bts (- n 1)). ... (combine-trees '(a b) ') should return the following ...
    (comp.lang.scheme)
  • Re: "mv" doesnt check for pre-existing destination
    ... When mv'ing across file systems, ... >the destination directory are not wiped out first. ... the source and destination file trees are merged. ... If someone has done a wee wrapper, ...
    (comp.unix.solaris)
  • Re: "mv" doesnt check for pre-existing destination
    ... the warning is *not* given when mv is ... When mv'ing across file systems, ... the destination directory are not wiped out first. ... the source and destination file trees are merged. ...
    (comp.unix.solaris)