That data structure can be actually used for a log structured database where the sparse vector is the log file and the dense vector is the record index.
The index of the dense vector is then the record identifier, and the dense vector contains the offset of the valid record in the log database.
The record identifier is a handle to the record data. It can be reused when the record is deleted but will remain the same for the lifetime of the record.
The dense vector is very compact and may be stored and retrieved efficiently, even if stored in the log itself. The record key index stores the association between the key and the record identifier.
The GC or crash recovery process can easily locate valid records by checking if their offset matches the one found in the dense index.
So this data structure is not just of historical interest. Thanks for the link.
The index of the dense vector is then the record identifier, and the dense vector contains the offset of the valid record in the log database.
The record identifier is a handle to the record data. It can be reused when the record is deleted but will remain the same for the lifetime of the record.
The dense vector is very compact and may be stored and retrieved efficiently, even if stored in the log itself. The record key index stores the association between the key and the record identifier.
The GC or crash recovery process can easily locate valid records by checking if their offset matches the one found in the dense index.
So this data structure is not just of historical interest. Thanks for the link.