[TOC] # 内存表 MemTable ## MemTable 中的数据结构 OceanBase 数据库的内存存储引擎 MemTable 由 BTree 和 Hashtable 组成，在插入/更新/删除数据时，数据被写入内存块，在 HashTable 和 BTree 中存储的均为指向对应数据的指针。  ## 两种数据结构的特点 <div id="QUhTD" data-tag="div" class="div"><table data-tag="table" id="table-heh-b9o-4xp" class="table"><colgroup width="96" span="1" data-tag="col" id="col-y7u-gbj-mu3" colwidth="1*" colnum="1" colname="col1" style="width:33.33333333333333%" class="col"></colgroup><colgroup width="310" span="1" data-tag="col" id="col-y59-n10-f98" colwidth="1*" colnum="2" colname="col2" style="width:33.33333333333333%" class="col"></colgroup><colgroup width="209" span="1" data-tag="col" id="col-5r2-xpk-e5r" colwidth="1*" colnum="3" colname="col3" style="width:33.33333333333333%" class="col"></colgroup><thead id="thead-qc4-efq-fs4" class="thead"><tr id="tr-hiy-asy-04z"><th id="td-21c-7kd-uc6"><p id="p-v1q-wqs-if0"><b>数据结构</b></p></th><th id="td-3tx-2ep-10c"><p id="p-m4j-h8q-k2f"><b>优点</b></p></th><th id="td-tcp-yjr-g5q"><p id="p-ty9-o4f-fi0"><b>缺点</b></p></th></tr></thead><tbody data-tag="tbody" id="tbody-4pi-cmh-7vn" class="tbody"><tr data-tag="tr" id="tr-euc-7ss-lrj" class="tr"><td data-tag="td" id="td-01h-fb8-13i" class="td"><p data-tag="p" id="p-t7w-xh5-csr" class="p">HashTable </p></td><td data-tag="td" id="td-6gx-xq4-7eo" class="td"><p data-tag="p" id="p-qnr-cci-dqv" class="p">插入一行数据的时候，需要先检查此行数据是否已经存在，当且仅当数据不存在时才能插入，检查冲突时，用 Hashtable 要比 BTree 快。</p><p data-tag="p" id="p-jx2-gjp-xoz" class="p">事务在插入或更新一行数据的时候，需要找到此行并对其进行上锁，防止其它事务修改此行，OceanBase 数据库的行锁放在 ObMvccRow 中，需要先找到它，才能上锁。</p></td><td data-tag="td" id="td-hop-ewj-lcf" class="td"><p data-tag="p" id="p-d3e-ogr-3aw" class="p">不适合对范围查询使用HashTable。</p></td></tr><tr data-tag="tr" id="tr-sdn-glc-88n" class="tr"><td data-tag="td" id="td-8wd-zo5-nr2" class="td"><p data-tag="p" id="p-dt0-b5t-h7d" class="p">BTree</p></td><td data-tag="td" id="td-gcd-tyg-4ab" class="td"><p data-tag="p" id="p-6vy-6y4-jxq" class="p">范围查找时，由于 BTree node 中的数据都是有序的，因此只需要搜索局部的数据就可以了。</p></td><td data-tag="td" id="td-69t-eur-q2z" class="td"><p data-tag="p" id="p-fju-q6c-7gn" class="p">单行的查找，也需要进行大量的 rowkey 比较，从根结点找到叶子结点，而 rowkey 比较性能是较差的，因此理论上性能比 HashTable 慢很多。</p></td></tr></tbody></table></div>