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 to the memory block. Hash tables and B-trees store the pointers to 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. Data checks for hash tables are faster than those for B-trees. When a transaction inserts or updates a row of data, it needs to find this row and lock it to prevent other transactions from modifying the row. Row locks in OceanBase Database are stored in the row header data structure. The transaction must find a row lock before it locks the row. | Hash tables are not suitable for range queries. |
| B-tree | Data in B-trees is ordered. This design allows OceanBase Database to search for only local data when it performs range queries. | Single-row queries require the comparison of a large number of primary keys from the root node to the leaf nodes. However, it is relatively difficult to compare primary keys in B-trees. In theory, the query speed in B-tree is much slower than that in hash tables. |