MemTable 中的数据结构

OceanBase 数据库的内存存储引擎 MemTable 由 BTree 和 Hashtable 组成,在插入/更新/删除数据时,数据被写入内存块,在 HashTable 和 BTree 中存储的均为指向对应数据的指针。

存储图片 1.png

两种数据结构的特点

数据结构

优点

缺点

HashTable

插入一行数据的时候,需要先检查此行数据是否已经存在,当且仅当数据不存在时才能插入,检查冲突时,用 Hashtable 要比 BTree 快。

事务在插入或更新一行数据的时候,需要找到此行并对其进行上锁,防止其它事务修改此行,OceanBase 数据库的行锁放在 ObMvccRow 中,需要先找到它,才能上锁。

不适合对范围查询使用HashTable。

BTree

范围查找时,由于 BTree node 中的数据都是有序的,因此只需要搜索局部的数据就可以了。

单行的查找,也需要进行大量的 rowkey 比较,从根结点找到叶子结点,而 rowkey 比较性能是较差的,因此理论上性能比 HashTable 慢很多。