本技术公开了应用于数据库存储的文件数据存储读取方法,包括文件数据存储,所述文件数据存储包括:将key‑value数据写到文件的数据区,记录在数据区的偏移和大小S[offset+size];计算key‑value数据中key的哈希值hash(key),更新位图bitmap中哈希值hash(key)对应的第hashID位的bit值;所述hashID,key,S[offset+size]作为key‑value数据写入时的哈希索引记录,并将所述哈希索引记录写入在文件中。本发明的应用于数据库存储的文件数据存储读取方法在进行数据存储时采用新的文件格式通过hash索引,在进行key值检索时时间复杂度可以达到O(1),极大的提升了key‑value数据的检索效率。
背景技术
KV数据库是指Key-value数据库,是一种以键值对存储数据的一种数据库。而为了提高数据库的查询速度,需要针对数据库建立数据库索引,针对KV数据库比较常见的三种数据库索引的数据结构:哈希表、有序数组和搜索树。
哈希表里面存储的是key-value键值对。利用哈希表来存储索引的话,得先利用哈希函数把key换算成数组中对应的一个Index位置,然后把value放在这个位置,如果多个key换算后得到了相同的index,那么就在这里追加一条链表,存储哈希值相同的key-value对象。如果给你一个指定的key让你查询对应的value,需要先根据哈希函数换算数组的index值,如果该位置有多个值,那么遍历链表即可。哈希表的缺点很明显,由于哈希表是无序的,所以哈希索引做区间查询的速度是很慢的。
有序数组在等值查询和范围查询场景中的性能就都非常优秀。key-value数组就是按照顺序保存的。这时候如果你要查key对应的value,用二分法就可以快速得到,这个时间复杂度是O(log(N))。采用二分法虽然能大大的提升查询的效率,但是O(log(N))的时间复杂度对于数据库的查询来说效率还有待提升,而且key-value数组是有序存储,在需要更新数据的时候就麻烦了,往中间插入一条记录还必须得移动后面所有的记录,成本太高。
搜索树,树是一种数据结构,它是由n(n>=0)个有限节点组成一个具有层次关系的集合,把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。搜索树查询一般采用二分法,时间复杂度是O(log(N))。
有鉴于此,本发明所要解决的技术问题是:如何提升KV数据库的查询效率,甚至于KV数据库查询的时间复杂度能够达到O(1),O(1)表示一次操作即可直接取得目标元素。
实现思路