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.

  • What programming language are you using to create this?
    – J.D.
    Commented Sep 6, 2022 at 12:31
  • @J.D. I use C as the programming language.
    – GenGG
    Commented Sep 6, 2022 at 14:33
  • Check out what SQLite does. Then, maybe look at PostgreSQL. Both written in ISO C!
    – Vérace
    Commented Sep 6, 2022 at 23:19
  • @Vérace Could you please give a link to the material describing how SQLite and PostgreSQL B+ tree works?
    – GenGG
    Commented Sep 7, 2022 at 2:19
  • PostgreSQL - start here and start here for SQLite. HTH!
    – Vérace
    Commented Sep 7, 2022 at 2:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.