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