Question #5 in the Berkeley DB Access Method FAQ says this:
```
I'm using integers as keys for a Btree database, and even though the key/data
pairs are entered in sorted order, the page-fill factor is low.
This is usually the result of using integer keys on little-endian architectures
such as the x86. Berkeley DB sorts keys as byte strings, and little-endian
integers don't sort well when viewed as byte strings. For example, take the
numbers 254 through 257. Their byte patterns on a little-endian system are:
254 fe 0 0 0
255 ff 0 0 0
256 0 1 0 0
257 1 1 0 0
If you treat them as strings, then they sort badly:
256
257
254
255
On a big-endian system, their byte patterns are:
254 0 0 0 fe
255 0 0 0 ff
256 0 0 1 0
257 0 0 1 1
and so, if you treat them as strings they sort nicely. Which means, if you use
steadily increasing integers as keys on a big-endian system Berkeley DB behaves
well and you get compact trees, but on a little-endian system Berkeley DB
produces much less compact trees. To avoid this problem, you may want to
convert the keys to flat text or big-endian representations, or provide your
own Btree comparison.
```
RPM+BDB currently uses a hash for secondary lookup and so is largely unaffected
as distributed.
However LMDB has only btree, and using little endian hdrNum comparison has the
following consequences:
* the distribution of keys across btree leaf nodes is sub-optimal
* the depth of search is biased, causing btree performance degradation because
of tall/skinny trees
* the ability of btree to always preserve keys in sorted order is lost. E.g. an
iteration across Packages does not return packages in the order installed even
though the hdrNum is most definitely assigned as a monotonically increasing
integer.
Both BDB and LMDB permit adding a custom btree comparison that can do the
comparison correctly.
The problem with customizing the comparison (instead of always using big endian
hdrNum) is that
the custom comparison MUST be configured for all accesses. This effectively
makes mdb_dump/mdb_load as distributed with LMDB useless (the tools could of
course be patched to add a custom comparison, but there's no easy way to force
only the modified tools to be used in the real world).
I will send a patch to fix the issue shortly. Making the effect of the patch
invisible to users is all that is hard.
--
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/rpm-software-management/rpm/issues/287
_______________________________________________
Rpm-maint mailing list
Rpm-maint@lists.rpm.org
http://lists.rpm.org/mailman/listinfo/rpm-maint
