Dawid,
> Other idea than using histogram_bounds would be using the
> position of key inside the index to determine the "ideal"
> place of row inside the table and find the closest free spot
> there. This would be of course much more precise and wouldn't
> rely on statistic.
This is generally known as "index organized tables" in other databases.
It implements a clustered storage of the table, which dramatically
speeds access on the chosen indexed column and makes inserts fast.
This also eases some of the visibility/MVCC implementation issues being
discussed on hackers, but does not help with the maintenance of
non-storage key indices.
Other DBMS have index organized tables that can use either hash or btree
organizations, both of which have their uses. We are planning to
implement btree organized tables sometime - anyone else interested in
this idea?
- Luke