OceanBase分布式存储引擎公共模块——基础数据结构OceanBase分布式存储引擎公共模块——基础数据结构

为了提高随机读取性能，updateserver支持创建哈希索引，这个哈希索引结构就是lightlyhashmap,代码如下：

lightlyhashmap采用链式冲突处理方法，即将所有哈希值相同的对链到同一哈希桶中，它包含如下三个方法：

insert：往哈希表中插入一个对。这个函数首先根据key 的哈希值得到桶号，接着，往哈希桶中插入一个包含key和value值的node节点。

get：根据key查找value。这个函数首先根据key的哈希值得到桶号，接着，遍历对应的链表，找到与传入key相同的node节点，返回其中的value值。

erase：根据key删除一个对。这个函数首先根据key的哈希值得到桶号，接着，遍历对应的链表，找到并删除与传入key相同的node节点。

lightlyhashmap设计用来存储几千万甚至几亿个元素，它与普通哈希表的不同点在于以下两点：

位锁（bitlock）：lightlyhashmap通过bitlock实现哈希值的锁结构，每个哈希桶的锁结构只需要占用一个位（bit）。如果哈希桶对应的位锁值为0.表示没有锁冲突；否则，表现出锁冲突。需要注意的是，lightlyhashmap没有区分读锁和写锁，多个get请求也是冲突。可以对lightlyhashmap的bitlock做一些改进，例如用两个位（bit）表示哈希桶对应的锁，其中一个位表示是否有读冲突，另外一个位表示是否有写冲突。

延迟初始化（lazy initialization）：lightlyhashmap的哈希桶个数往往特别多（默认为1000万个），即使仅仅对所有哈希桶执行一次memset操作，消耗的时间也是相当可观的。因此，lightlyhashmap采用延迟初始化的策略，即将哈希桶划分为多个单元，默认情况下每个单元包含65536个哈希桶。每次执行insert、get或者erase操作时都会判断哈希桶所属的单元是否已经初始化，如果未初始化，则对该单元内的所有哈希桶执行初始化操作。

updateserver的memtable结构底层采用b树结构索引其中的数据，代码如下：

支持的功能如下：

put:插入一个对。

get：根据key获取对应的value。

scan:扫描一段范围内的数据行。首先，调用get_scan_handle获取扫描操作描述符，其次，调用set_key_range设置扫描的数据范围，最后，不断地diao'yon调用get_next读取下一行数据直到全部读完。

为了提高读写并发能力，b树实现时采用写时复制（copy-on-write）技术，修改每个索引节点时首先将该节点拷贝出来，接着在拷贝出来的节点上执行修改操作，最后在原子地修改其父节点的指针使其指向拷贝出来的节点。这种实现方式的好处在于修改操作不影响读取，读取操作永远不会被阻塞。