On Fri, Aug 5, 2011 at 5:21 AM, Hannes Streicher <[email protected]> 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]
