A database operable in a multithreaded environment has a database update code. Each thread accessing the database obtains lock prior to walking the database. Any thread that alters database structure, such as by adding or deleting a record of the database, writes the database update code. Before releasing lock, the thread copies the database update code and a current record pointer into memory locations private to the thread. When a thread requires a second access to a record of the database, it obtains lock. The thread then compares its copy of the update code to the database update code, if they are different the thread must re-walk the database to locate the record since database structure has changed since the thread first accessed the database. If the thread's copy of the update code matches the database update code, database structure has not changed since a prior access of the thread to the database; in this case the record may be accessed through the thread's copy of the record pointer with no walk required. In a particular embodiment, the database is accessed through a hash table and contains firewall connection and filter rule information.