Re: [Caml-list] [1/2 OT] Indexing (and mergeable Index-algorithms)

[Florian Weimer <fw@deneb.enyo.de>]

* Oliver Bandel:

> So, say we have 10^6 texts that we want ot have an index for,
> to retrieve the text according to some parts of the text
> (keywords, substrings,...).
> We want to make an index from these texts.

B-trees are often used for that purpose.

> After a while we get 10^5 new texts and want to extend
> the exisiting index, so that the whole index not necessarily
> must be created again, with the indexer-tool running on
> all files (^10^6 + 10^5) again, but only have to index the new files,
> but the big index can be extended with additional smaller indizes.

10^6 documents won't fit into available RAM.  What's worse, you cannot
afford to reindex everything just because the machine crashed.  This
means that you need some form of crash recovery (e.g. write-ahead
logging).

> Is there something like that already existing?

Plenty.  Berkeley DB, SQLite, full-blown SQL database servers like
PostgreSQL or MySQL.  The list is pretty long.

> It's mainly a question on datastructures/algorithms, so this mailing list
> may be the wrong, but the reason to aske here is: Are functional
> datastructures in some way good for implementing such tools?

They are called "log-structured databases".  Typically, they offer
superior write performance (especially if you can waste a lot of disk
space and delay garbage collection), but read access cannot match
performance of more traditional approaches (like B-trees plus
write-ahead logging).

> (Maybe using OCaml, but the imperative features of it would help,
>  if the functional features would be too slow?)

If I were you, I'd reuse existing libraries (not written in Objective
Caml), so this question wouldn't be relevant.