I implemented a heap with MVCC; that is, each tuple in the heap has a history list so that updating the tuple does not block reading. I also implemented a secondary B+ tree; that is, it stores (primary key, RID) in its leaves, where RID is the address of the tuple with the primary key in heap. I use the following locking scheme in my implementation of B+ tree search, insertion and deletion (mark deletion actually).
Search: When the search key is found, an S-lock on the search key is requested. Once acquired, if the search key is not marked as deleted, the corresponding RID is used to access the tuple in the heap.
Insertion: After having found the leaf to accommodate the inserted key, an X-lock on the inserted key is requested. Once acquired, if the key is not present, the key is inserted into the leaf; otherwise, a uniqueness violation is issued.
Deletion: After having found the leaf where the key to delete resides, an X-lock on the deleted key is requested. Once acquired, if the key is present and not marked deleted, the key is delete-marked.
My Question: My current implementation obviously does not guarantee "writing does not block reading" of MVCC. To see this, suppose transaction T1 deletes the key "hello" and transaction T2 at the same time wants to read the key "hello". In MVCC, T2 will not be blocked; it reads the corresponding history list of "hello". However, in my implementation, T2 will be blocked since it needs to request an S-lock on "hello" (B+ tree search) which has been X-locked by T1 already (B+ tree deletion). I wonder if there is any better way to do the locking for the B+ tree.
P.S. I considered not using S-lock in search. In that case, for a delete-marked entry (key, RID), it is not possible to tell if the entry has been committed. If the entry has been committed, RID may be invalid since the corresponding tuple may have been removed from the heap. If the entry has not yet been committed, RID is still valid and thus can be used to visit the heap.
