In module \lib\bsddb\__init__.py line 147, the method set_location() uses self.dbc.set(key) , which raises an error if the key is not found. It should be using self.dbc.set_range(key) , which matches the documented behaviour for btree databases. Test for correct behaviour is attached. Behaviour is seen under Python 2.3.3 win32 binary build.