Does B-tree in InnoDB use mark-delete?

Question

I learnt that all secondary B-trees in InnoDB store pairs of the form (search key, TID) where TID is the primary keys of the records. I have the following questions:

(1) In InnoDB, does the secondary B-trees implement deletion by mark-deletion? That is, the entries in the leaves are marked as deletion instead of physical deletion.

(2) If so, when inserting a new entry whose search key is the same as some existing mark-deleted entry, how does InnoDB decide if the mark-deleted entry has been committed or not? For example, suppose the B-tree is a unique index. Suppose the first transaction mark-deletes search key hello, and the second transaction tries to insert search key hello. If the first transaction has not yet committed, the insertion should be failed; otherwise, the insertion should be successful. I wonder how InnoDB decides if it is allowed to insert hello.

Answer 1

Mostly "no" to your questions.

Let me go over several aspects of how InnoDB handles secondary indexes.

• They are stored in "B+Trees" (see Wikipedia), just like the data.
• The data B+Tree is ordered by the PRIMARY KEY.
• Each secondary index (whether UNIQUE or not) is stored in a separate B+Tree, ordered by the key(s) defined in the index.
• The BTrees are 16KB (by default). So, on the order of 100 data or index 'rows' can be held in a block.
• Since fetching a block (from disk, or locating it in the buffer_pool (cf "innodb_buffer_pool_size")) is the bulk of the effort, there is no concept of 'marking' for later delete.
• UNIQUE keys are checked early in transaction processing; a duplicate will lead to either a "lock wait timeout" or a "deadlock" or "duplicate key error".
• Non-Unique indexes are staged/cached in the "Change Buffer", which is allocated in a part (25% by default) of the buffer_pool. This has a list of pending index changes (insert/update/delete). They are collected, sorted, and eventually used to update index blocks.
• The goal of the change buffer is to diminish I/O for index changes. It has the effect of being more efficient at handling deletes.
• So, in a way, the change buffer is how it 'marks for delete'.
• In the data BTree, a "history list" is kept of pending changes to the data. This is a core component of how MVCC works and how multiple transactions can successfully work in various "transaction isolation modes", even when some transactions are eventually ROLLBACK'd.

There is probably more.

The quoted things are key topics to research further in the MySQL literature.