btree

The db(3) form of database

V8.1 and above

The term btree stands for "balanced tree." It is a grow-only form of database. Lookups and insertions are fast, but deletions do not shrink the size of the database file.^[8] A good description of this form of database can be found in The Art of Computer Programming, Vol. 3: Sorting and Searching, D.E. Knuth, 1968, pp. 471-480. The btree type is available only if sendmail was compiled with NEWDB defined and the Berkeley or Sleepycat db library linked (Section 3.1.2). In most cases, the hash type (hash) will perform slightly better.

^[8] However, space is reclaimed in the file for future use.

Quite a few database switches are available with this database-map type. They are listed in Table 23-7.

Table 23-7. The btree database-map type K command switches
Switch	§	Description
`-A`	-A	Append values for duplicate keys
`-a`	-a	Append tag on successful match
`-D`	-D	Don't use this database map if DeliveryMode=defer
`-f`	-f	Don't fold keys to lowercase
`-m`	-m	Suppress replacement on match
`-N`	-N	Append a null byte to all keys
`-O`	-O	Never add a null byte
`-o`	-o	The database map is optional
`-q`	-q	Don't strip quotes from key
`-S`	-S	Space replacement character
`-T`	-T	Suffix to append on temporary failure
`-t`	-t	Ignore temporary errors

One use for this btree type might be to look up users for whom permission is denied to send offsite email. The data source file might look like the following, and might live in the file /etc/mail/badusers.db (after makemap was run to create it):

bob    bob
ted    ted
alice  alice

A simple configuration file to test this database can then be created like this:

V10
Kbaduser btree -a.BAD -t /etc/mail/badusers
R $+ < @ $+ > $*                    $: $1< @ $2 > $3 < $(baduser $1 $) >
R $+ < @ $+ > $* < $* . BAD >       $#error $@ 5.1.3 $: "Offsite mailing denied"

Here, the database is declared with the K configuration command. The -a database switch causes .BAD to be appended to any key that is found in the database. The -t switch causes temporary errors to be ignored. A match causes the workspace to carry the extra information that is matched by <$*.BAD >, and which results in an error being reported back to the sender.

The -d38.20 command-line switch (-d38.20) can be used to observe this type's lookups in more detail.

Table 23-7. The btree database-map type K command switches