How to configure OpenLDAP 2.4 with bdb backend?

It looks like you haven't loaded this module. Uncomment/insert the belows line to slapd.conf:

modulepath /usr/lib/ldap
moduleload back_bdb.la

I recently helped my coworker do the same thing, and this is what i found to be the quick and easy solution (on a clean install) using the new configuration backend. This was on a RHEL server, but it should be similar on whatever you are running.

Stop slapd and check what your configuration db admin dn + password is

[root@ldap openldap] cd /etc/openldap/slapd.d/cn\=config
[root@ldap cn=config]# egrep "olcRootDN|olcRootPW" "olcDatabase={0}config.ldif"
olcRootDN: cn=admin,cn=config
olcRootPW: secret

If olcRootPW is not present in the file add it, and start slapd again. You'll need some ldif to create your new bdb database

[root@ldap ldap]# cat bdb.example.com.ldif
# Load modules for database type
dn: cn=module,cn=config
objectclass: olcModuleList
cn: module
olcModuleLoad: back_bdb.la
# Create directory database
dn: olcDatabase=bdb,cn=config
objectClass: olcDatabaseConfig
objectClass: olcBdbConfig
olcDatabase: bdb
olcSuffix: dc=example,dc=com
olcDbDirectory: /var/lib/ldap
olcRootDN: cn=admin,dc=example,dc=com
olcRootPW: admin
olcDbIndex: uid pres,eq
olcDbIndex: cn,sn,mail pres,eq,approx,sub
olcDbIndex: objectClass eq
# Allow users to change their own password
# Allow anonymous to authenciate against the password
# Allow admin to change anyone's password
olcAccess: to attrs=userPassword
    by self write
    by anonymous auth
    by dn.base="cn=admin,dc=example,dc=com" write
    by * none
# Allow users to change their own record
# Allow anyone to read directory
olcAccess: to *
    by self write
    by dn.base="cn=admin,dc=example,dc=com" write
    by * read

And just insert that with ldapadd using your admin dn + password

[root@ldap ldap]# ldapadd -h localhost -D "cn=admin,cn=config" -W -f bdb.example.com.ldif
Enter LDAP Password:
adding new entry "cn=module,cn=config"
adding new entry "olcDatabase=bdb,cn=config"

You can change configuration in the slapd.d files just like you would do with slapd.conf, even though it is not recomended.