Described are a system and method of providing simultaneous lock-free access by a write process and at least one read process to records. The records are organized according to a first search data structure and according to a second search data structure. When searching for a particular record, the search occurs along a search path determined by the first search data structure until a record is accessed that indicates that the first search data structure is in an intermediate state. The searching for the particular record then continues along a search path determined by the second search data structure in response to the record that indicates that the first search data structure is in an intermediate state.