买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网获悉中国科学技术大学申请的专利一种基于多日志结构合并树的键值存储方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN117573634B 。

龙图腾网通过国家知识产权局官网在2026-03-24发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202311545478.8，技术领域涉及：G06F16/18；该发明授权一种基于多日志结构合并树的键值存储方法是由李永坤;卓凯;许胤龙设计研发完成，并于2023-11-20向国家知识产权局提交的专利申请。

本一种基于多日志结构合并树的键值存储方法在说明书摘要公布了：本发明公开了一种基于多日志结构合并树的键值存储方法，包括：1、多日志结构合并树MLSMT接收到读写请求时，根据请求中键的哈希值，判断键所属的日志结构合并树LSMTi，并在LSMTi执行读写操作；2、MLSMT结构接收到扫描请求时，对日志结构合并树中的文件建立分组迭代器，使用并行线程执行键的定位操作Seek，使用堆排序查找下一个key，从而读出数据；3、后台使用并行线程处理Compaction操作，并根据元数据信息将属于当前LSMTi的数据从分裂出LSMTi的LSMTs中读出，写入到LSMTi的SST文件中。本发明能实现数据的加速写入和归并，减少单个日志结构合并树层数，从而提高系统的读写性能。

本发明授权一种基于多日志结构合并树的键值存储方法在权利要求书中公布了：1.一种基于多日志结构合并树的键值存储方法，其特征是应用于设置有MLSMT结构的单个存储节点中，所述MLSMT结构包括：Compaction调度器、LSMT信息监控器、N个日志结构合并树{LSMT1,LSMT2,…,LSMTi,…,LSMTN}，其中，LSMTi表示第i个日志结构合并树；1≤i≤N； 所述第i个日志结构合并树LSMTi包含一个磁盘组件和内存组件； LSMTi中的磁盘组件包含P个层结构{Li1,Li2,…,Lij,…,Lip}，其中，Lij表示第i个日志结构合并树的第j层结构，1≤j≤P；第j层结构Lij包括Qij个SST文件{SSTij1,SSTij2,…,SSTijk,…,SSTijQij}，其中，SSTijk表示第i个日志结构合并树LSMTi的第j层结构Lij的第k个SST文件，1≤k≤Qij； 第k个SST文件SSTijk包含若干键值数据key,value，根据第k个SST文件SSTijk中所有键数据key的取值，得到第k个SST文件SSTijk的键范围keyminijk,keymaxijk，其中，keyminijk表示第k个SST文件SSTijk的键的最小值，keymaxijk表示第k个SST文件SSTijk的键的最大值，除第1层结构Li1的各文件之间键范围有重叠外，其他层结构的各文件之间的键范围无重叠且有序排列； 令第k个SST文件SSTijk中所有键值数据所占磁盘空间大小记为第k个SST文件SSTijk的大小Sizeijk，第j层结构Lij所有SST文件的总大小Sizeij的阈值记为LimitSizeij，j1，第1层结构的SST文件个数具有阈值LimitNumi； 除第1层结构Li1外，第j+1层结构Lij+1中所有SST文件的阈值LimitSizeij+1是第j层结构Lij中所有SST文件的阈值LimitSizeij的q倍，即LimitSizeij+1=q×LimitSizeij； 所述第i个日志结构合并树LSMTi的内存组件包括内存缓冲区MTi、内容不可变的缓冲区IMTi，二维元数据管理数组FMi，且FMi中包含P×Qij个元素，每个元素是由SST文件的编号、SST文件的大小、SST文件的引用计数、键的最小值、键的最大值，是否垃圾回收的标志字段GC组成的结构体； 所述第i个日志结构合并树LSMTi包含的操作为：FHi操作、Compactioni操作；其中，Compactioni操作分为MinCi操作、MaxCi操作； FHi操作是指内存缓冲区MTi中的键值数据以SST文件的形式写入磁盘组件的第1层结构Li1中； MinCi是指第1层结构Li1和第2层结构Li2所选取的SST文件按键排序、合并后划分成新的SST文件后写入Li2； MaxCi是指第j层结构Lij和第j+1层结构Lij+1所选取的SST文件按键排序、合并后划分成新的SST文件后写入Lij+1；j1； 所述LSMT监控器用于获取N个日志结构合并树的监控信息并计算分裂指标，令Fi为第i个日志结构合并树LSMTi的分裂指标，Fit为第i个分裂指标的阈值；第i个日志结构合并树LSMTi的监控信息包括：LSMTi所有SST文件所占磁盘空间大小总和Si、磁盘空间大小阈值Sit、读写请求次数RWi，以及所有日志结构合并树的读写请求总数RW； 所述键值存储方法是按如下步骤进行： 步骤1、当前线程利用所述MLSMT结构接收外部的读写数据的请求req，并判断请求req的种类： 若请求req是写请求Write，则执行步骤2，其中，所述写请求Write中的参数包括若干要写入的键值数据key,value； 若请求req是读请求Get，则执行步骤2；其中，所述读请求Get中的参数包括若干键数据key； 若请求req是扫描请求Scan，则执行步骤5；其中，所述扫描请求Scan中的参数包括键数据范围key1,key2； 步骤2、后台线程执行日志结构合并树的分裂指标的计算和分裂； 步骤2.1、根据LSMTi的监控信息、计算分裂指标，其中，P1、P2分别代表每部分的权重比例； 步骤2.2、判断FiFit是否成立，若成立，则执行步骤2.3；否则，从LSMTi中分裂出一个新的日志结构合并树LSMTi’，并将LSMTi的二维元数据数组FMi拷贝一份作为分裂出的日志结构合并树LSMTi’的元数据数组FMi’，并更新N为N+1； 步骤2.3、则将i+1赋值给i后，返回步骤2.1，直至iN，再将1赋值给i，返回步骤2.1执行； 步骤3、当前线程对请求req中的键key进行哈希运算得到相应的哈希值，所述哈希值对阈值mod进行取模运算后得到中间值hv，其中，mod表示日志结构合并树数量的阈值； 步骤4、当前线程计算用于表示N所需的二进制位数的最小值n，并根据n计算hv的二进制尾部的n位值，再根据n位值计算日志结构合并树的序号i，从而令请求req中的键key属于LSMTi； 若请求req为写请求Write，则执行步骤A1和步骤B1： A1、将写请求Write中参数对应的键值数据写入MTi，并按照步骤A1.1-A1.5执行； A1.1、判断第i个日志结构合并树LSMTi的内存缓冲区MTi的大小Msizei是否大于阈值Mmax，若大于，则执行步骤A1.2；否则，将参数key,value所对应的键值数据写入到LSMTi的内存缓存区MTi，并执行B1； A1.2、判断当前日志结构合并树LSMTi的IMTi是否为空，若不为空，则等待，直到Compaction调度器执行FHi操作的调度请求，从而将缓冲区IMTi中所有数据写入磁盘中，使得IMTi变为空，否则，执行A1.3； A1.3、将IMTi指向当前内存缓冲区MTi，并生成新的空的内存缓冲区，使得MTi指向新的内存缓冲区； A1.4、当前线程生成FHi操作的调度请求，将请求插入Compaction任务队列中，并返回步骤1，以接收下一个请求req； A1.5、后台线程利用Compaction调度器执行FHi操作的调度请求，然后生成Compactioni操作的调度请求，并将请求插入Compaction任务队列中，等待Compaction调度器执行Compactioni操作的调度请求； B1、更新LSMTi的监控信息中的参数Si、RWi、RW，即Si增加写请求Write的键值数据的大小，RWi增加写请求Write的键值数据的数量，并重新计算RW后，返回步骤1，以接收下一个请求req； 若请求req为读请求Get；则执行步骤A2-D2： A2、更新LSMTi的监控信息中的参数RWi、RW，即RWi增加读请求Get中键key的数量，并重新计算RW的值； B2、在LSMTi的内存缓冲区MTi中查找读请求Get中的键key，若找到，则返回对应的值value；否则，执行C2； C2、在LSMTi的内容不可变的内存缓冲区IMTi中查找读请求Get中的键key，若找到，则返回对应的值value；否则，执行D2； D2、从LSMTi的磁盘组件的第1层结构开始查找读请求Get中的键key，若在任意第j层结构中找到，则返回对应的值value，否则，继续遍历下一层结构，直到查找完第P层结构为止，若始终未找到，则返回空； 步骤5、在MLSMT结构中处理Scan请求，执行步骤A3-C3： A3、当前线程对MLSMT中的每个日志结构合并树分别建立若干个迭代器，并将所有迭代器划分成G个迭代器组，将每个迭代器组合并为一个MergeIter迭代器； B3、使用多线程并行处理每个MergeIter迭代器的seek操作，即将每个MergeIter迭代器均指向第一个大于等于扫描请求Scan中键key1的位置； C3、使用堆排序对所有MergeIter迭代器所指向的位置的键大小进行升序排序，并判断最小键keymin是否大于key2，若大于，返回步骤1，以接收下一个请求req；否则，输出最小键keymin，并将keymin所对应的MergeIter迭代器往键大小的升序方向移动一个位置，更新keymin所对应的Mergeiter迭代器的键大小，再重复执行C3。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人中国科学技术大学，其通讯地址为：230026 安徽省合肥市包河区金寨路96号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。

以上内容由龙图腾AI智能生成。