On Fri, Aug 5, 2011 at 5:21 AM, Hannes Streicher <hstreicher@...> wrote:

> Guten Tag Lester Caine,
>
> am Freitag, 5. August 2011 um 10:50 schrieben Sie:
>
> > A thought just popped up ... with some fairly simple replication, the
> 'active'
> > database might be able to 'insert' into the read only? If we are only
> adding to
> > the end of a list controlled by a generator sourced ID then the indexes
> should
> > just 'insert' at the end? But of cause I'm forgetting that we need to
> update
>
> there is no "Insert to the end of an Index" Index will be rebalanced every
> now and
> then upon an insert/update/delete which can will likely produce a lot of
> writes.
>

OK, you're both wrong about the way Firebird indexes work. Somewhere on the
IBPhoenix site there are a couple of articles I wrote years ago describing
their design in painful detail - generally correctly. But here's the short
version.

An index starts as a single page which starts with some internal indexing
for that page, followed by entries consisting of a header, key value, and a
record id. The entries are variable length - which is why there's a
page-level index at the front. With fixed length entries, you can do a
binary search on the page, but compressing the key values saves a lot of
space.

When the first page fills up, Firebird creates two new pages - one just like
the first, and one slightly different. The two identical pages are called
level 0 pages. The other one is a level 1 page and also contains a
page-level index and a string of varying length entries. The level 1
entries consist of a header, a key value, a record number, and a pointer to
the level 0 page that starts with that key value and record number. The
entries from the first level 0 page are split between the first page and
second, unless the entry that caused the page to overflow would have been
the last one on the page, in which case it goes on the new page alone. The
reason for that should be obvious.

Eventually, the index grows to the point that the level 1 page overflows.
Then Firebird creates a level 2 index page with the same format as the
level 1, except that the page pointers go down to level 1 pages rather than
level 0. When an index page drops below a certain fill level, Firebird
checks to see if the adjacent page is also below that fill level and
combines the two, removing the entry in the next level up that pointed to
the second (right hand) page. Recombination is done at every level.

A Firebird index is always balanced, with all record level entries at the
bottom and each one exactly the same distance from the top of the index. At
no point is the index re-balanced causing lots of writes. At most, one new
page is created for each level in the index plus one new top level page.
Neither is adding an entry just a question of appending, since all writes
are done as pages, so most insertions cause a page to be updated.


[Non-text portions of this message have been removed]