| Thanks for the help on indexing. The suggestions were similar
to what I'd been thinking of, so maybe I'm not so far off
the mark after all. Here's the plan:
For unique indexes, the index information information will be
stored along with the record as a binary tree:
- Pointer to parent node
- Pointer to lesser-than node
- Pointer to greater-than node
For indexes in which the indexed data is not unique, here's
how the information will be stored. There will be a
separate
table for unique nodes: each unique value is stored in a record
and is organized in a binary tree. That index table works just
like regular tables, except that is doesn't store the first or
last record positions or the previous and next positions in
each record. Each index record contains:
- The data being indexed
- Pointer to parent node
- Pointer to lesser-than node
- Pointer to greater-than node
- Pointer to last data record
- Pointer to first data record
Each data record contains:
- The data being indexed
- Pointer to previous record with identical index value (first
record points to index node)
- Pointer to next record with
identical index value (last record points to index node)
Eventually I'll implement red-black balancing, but that will
be a little bit down the road.
In case anybody is interested, I'm programming a
small-footprint, single-file database in Perl. I don't feel
that the current open-source databases out there meet the needs
of the average user in terms of simplicity of database
creation and use. Besides, I've always wanted to try prgramming
a DBA system from scratch. Anybody who is interested
in helping out is welcome to contact me.
-Miko | 
