Data structure in a MemTable
The memory storage engine (MemTable) of OceanBase Database consists of B-trees and hash tables. When data is inserted, updated, or deleted, the data is written into the memory block. Hash tables and B-trees store the pointers to the corresponding data.
Characteristics of the two data structures
| Data structure | Advantages | Disadvantages |
|---|---|---|
| Hash table | Before OceanBase Database inserts a row of data, it checks whether this row of data already exists. OceanBase Database inserts the data only when it does not exist. Hash Table is faster than B-tree in data check. When a transaction inserts or updates a row of data, it needs to find this row and lock it, preventing other transactions from modifying the row. Row locks in OceanBase Database are stored in ObMvccRow. The transaction must find a row lock before locking the row. |
Hash tables are not suitable for range queries. |
| B-tree | Data in the B-tree node is ordered. This design allows OceanBase Database to search some of the data when processing range queries. | Single-row queries require the comparison of a large number of rowkeys from the root node to the leaf nodes. However, it is relatively difficult to compare rowkeys in B-trees. Theoretically, the query speed in B-tree is much slower than that in hash tables. |