slapadd(8), database order

["Howard Chu" <hyc@highlandsun.com>]

We need to add some back-bdb specific notes to this manpage, but I wasn't
sure how I wanted to word it.

slapadd accepts LDIF input in slapcat/database order. When B-trees are used,
database order is actually the same as the original input order, it is not
random/unpredictable as with the hash database.

In back-bdb it is important that slapadd's input be well-ordered, with
superior entries added before child entries. If entries are added in random
order, the subtree index will quickly become useless as it grows in size.
When a subtree index slot gets large enough to be converted from an explicit
list into a range, the number of entries represented by the range can far
exceed the number of entries represented by the list.

For example, you may have an explicit list with IDs 10, 500, 999999. When
this list grows large enough to be converted into a range, instead of going
from 65536 IDs to 65537 IDs, this list will cover 999990 IDs just from adding
one ID to the list, and the vast majority of the IDs probably aren't in the
subtree of interest.

This situation can also arise during the life of a DIT from various ldapadd
operations, but if you start with a well-ordered input to slapadd it will
take a long time before it becomes a problem. In particular, when you start
with well-ordered input, it will be impossible for a subtree index slot to
erroneously include a superior node's ID. With a random input, there are no
such guarantees.

  -- Howard Chu
  Chief Architect, Symas Corp.       Director, Highland Sun
  http://www.symas.com               http://highlandsun.com/hyc
  Symas: Premier OpenSource Development and Support