lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


And if a small fixed number of tables with varying sizes is still not
enough for the goals, you can extend this scheme to use B-trees: each
page of a B-tree can be sequential or hashed subtable, and pages can
have a predefined maximum size to store for example up to 1024 values
in sequential subtables, or up to 512 values in hashed subtables (in
pages of B-trees used as hashed subtables, the mapping from an key's
hashvalue to a slot in the hashed subtable should use different bits
from the hash value, depending on the page depth in the tree:
rehashing keys will ne needed only for keys that are moved up or down
from one level to another, during B-tree management)

B-trees with fixed but tunable pages sizes and tunable fill factors
(for all depths or for some specific depths ouside the root level) are
used in relational databases in their storage. Their advantage is that
they minimize the number of reshaping operations needed, and they can
also optimize how keys in the same page are represented (e.g. for
string keys, their common initial part may be compacted, allowing more
keys to be stored in that page depending on each key length and how
their values are ditinguished; database engines can also use
datacompression in each pages to allow more compaction of large
volumes of keys in their index, they may also store some or all
values, not necessarily only other indexed keys, inside the same page
for "clustered" indexes, by dedicating an minimum size reserved for
the keys, and placing values if possible in the rest of the page
instead of separate data-only pages).