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