MemTableのデータ構造
OceanBaseデータベースのメモリストレージエンジンであるMemTableは、BTreeとHashtableで構成されています。データの挿入・更新・削除時には、データがメモリブロックに書き込まれ、HashTableとBTreeに格納されているのはそれぞれ対応するデータへのポインタです。
二つのデータ構造の特徴
データ構造 |
利点 |
欠点 |
|---|---|---|
| HashTable | 行データを挿入する際、まずその行データが既に存在するかどうかをチェックする必要があります。データが存在しない場合にのみ挿入できます。競合チェック時、HashtableはBTreeよりも高速です。トランザクションが行データを挿入または更新する際、その行を見つけてロックをかける必要があり、他のトランザクションによるその行の変更を防ぎます。OceanBaseデータベースの行ロックは行頭のデータ構造に配置されており、ロックをかける前にまずそれを見つける必要があります。 | HashTableは範囲クエリには適していません。 |
| BTree | 範囲検索時、BTree内のデータはすべて順序付けられているため、局所的なデータのみを検索すれば済みます。 | 単一行の検索でも、大量の主キー比較が必要です。根ノードから葉ノードまでたどる必要があり、主キー比較のパフォーマンスは低いため、理論上はHashTableよりもはるかに遅くなります。 |