WO2021159711A1 - 一种b+树的存取方法、装置和计算机可读存储介质 - Google Patents

一种b+树的存取方法、装置和计算机可读存储介质 Download PDF

Info

Publication number
WO2021159711A1
WO2021159711A1 PCT/CN2020/117331 CN2020117331W WO2021159711A1 WO 2021159711 A1 WO2021159711 A1 WO 2021159711A1 CN 2020117331 W CN2020117331 W CN 2020117331W WO 2021159711 A1 WO2021159711 A1 WO 2021159711A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
tree
level
node
file
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/CN2020/117331
Other languages
English (en)
French (fr)
Inventor
来炜国
刘志勇
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Suzhou Wave Intelligent Technology Co Ltd
Original Assignee
Suzhou Wave Intelligent Technology Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Suzhou Wave Intelligent Technology Co Ltd filed Critical Suzhou Wave Intelligent Technology Co Ltd
Priority to US17/799,878 priority Critical patent/US11762827B2/en
Priority to EP20919043.8A priority patent/EP4105770B1/en
Publication of WO2021159711A1 publication Critical patent/WO2021159711A1/zh
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2246—Trees, e.g. B+trees
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/10—File systems; File servers
    • G06F16/13—File access structures, e.g. distributed indices
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/061—Improving I/O performance
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0638—Organizing or formatting or addressing of data
    • G06F3/0643—Management of files
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0646—Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
    • G06F3/0647—Migration mechanisms
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671—In-line storage system
    • G06F3/0683—Plurality of storage devices
    • G06F3/0685—Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671—In-line storage system
    • G06F3/0673—Single storage device
    • G06F3/0679—Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Definitions

  • the present invention relates to the field of data storage technology, in particular to a B+ tree access method, device and computer readable storage medium.
  • all-flash arrays In the all-flash array storage system, due to the particularity of its structure, a large number of B+ tree structures are used. For example, all-flash arrays generally adopt thin provisioning. The logical address of the volume and the physical address of the volume on the disk array (Redundant Arrays of Independent Disks, RAID) are no longer linearly corresponding, but change. Becomes an approximate random mapping relationship. In order to manage this mapping relationship, the B+ tree is used to save the mapping from the volume logical address to the physical address, and the B+ tree is used to save the inverse mapping from the physical address to the logical address. The deduplication function of the all-flash array uses a B+ tree to save the mapping from the HASH value of the data block to the physical address.
  • RAID Redundant Arrays of Independent Disks
  • DRAM Dynamic Random Access Memory
  • SSD Solid State Drives
  • the purpose of the embodiments of the present invention is to provide a B+ tree access method, device and computer readable storage medium, which can improve the B+ tree read and write efficiency.
  • an embodiment of the present invention provides a B+ tree access method, including:
  • the data with the number of layers in the B+ tree greater than or equal to the preset threshold is stored in a preset storage area.
  • the B+ tree corresponds to a first level, a second level, and a third level; wherein the data of the first level is used as the bottom data;
  • storing data in the B+ tree greater than or equal to the preset threshold in a preset storage area includes:
  • the data of the third level of the B+ tree is stored in a preset hard disk.
  • the method further includes:
  • the minimum read and write granularity of the DCPMM memory is taken as the node capacity of the B+ tree.
  • the storing the bottom-level data of the B+ tree in the bottom-level tree file includes:
  • the bottom-level data of the B+ tree is stored in the bottom-level tree file according to the node capacity, and each node data is stored; wherein the key-value pair of each node data stores the offset address of the next-level node.
  • it also includes:
  • the root node is determined according to the logical address carried in the data query instruction
  • it also includes:
  • the method further includes:
  • the data mapped to the DRAM memory with the dirty flag set is migrated to the DCPMM memory.
  • the embodiment of the present invention also provides a B+ tree access device, including a first judgment unit, a first storage unit, a creation unit, and a second storage unit;
  • the first judging unit is used for judging whether there is an idle underlying tree file mapped to the DRAM memory when the B+ tree creation instruction is obtained; if it is, trigger the first storage unit; if not, trigger the creation unit;
  • the first storage unit is configured to store the bottom-level data of the B+ tree to the bottom-level tree file
  • the creating unit is configured to create a new target bottom-level data file, and map the target bottom-level tree file to DRAM memory, so as to store the bottom-level data of the B+ tree in the target bottom-level tree file;
  • the second storage unit is configured to, when the number of layers of the B+ tree is greater than or equal to a preset threshold, store data with the number of layers in the B+ tree greater than or equal to the preset threshold to a preset Storage area.
  • the B+ tree corresponds to a first level, a second level, and a third level; wherein the data of the first level is used as the bottom data;
  • the second storage unit is specifically configured to store the data of the second level of the B+ tree into the DCPMM memory; and store the data of the third level of the B+ tree into a preset hard disk.
  • it also includes as a unit;
  • the serving unit is used to use the minimum read and write granularity of the DCPMM memory as the node capacity of the B+ tree.
  • the first storage unit is specifically configured to store the bottom-level data of the B+ tree in the bottom-level tree file according to the node capacity; wherein the key-value pair of each node data is stored There is the offset address of the next level node.
  • it further includes a query unit, a determination unit, and a reading unit;
  • the query unit is configured to determine the root node according to the logical address carried in the data query instruction when the data query instruction is obtained;
  • the determining unit is configured to determine a leaf node according to the offset address contained in the root node
  • the reading unit is used to read the data corresponding to the leaf node.
  • it further includes a second judgment unit, a modification unit, a setting unit, a third judgment unit, and a reading unit;
  • the second judging unit is configured to judge whether there is node data matching the node identifier carried in the data modification instruction in the DRAM memory when the data modification instruction is obtained; if so, trigger the modification unit ; If not, trigger the third judgment unit;
  • the modification unit is configured to modify the node data according to the data to be replaced carried in the data modification instruction,
  • the setting unit is used to set a dirty flag on the modified node data
  • the third determining unit determines whether there is node data in the DCPMM memory that matches the node identifier carried in the data modification instruction;
  • the modification unit is further configured to: when there is node data in the DCPMM memory that matches the node identifier carried in the data modification instruction, perform data modification on the node according to the data to be replaced carried in the data modification instruction.
  • Data modification
  • the reading unit is configured to, when there is no node data in the DCPMM memory that matches the node identifier carried in the data modification instruction, compare the hard disk with the node data carried in the data modification instruction Read the node data matching the identifier into the DRAM memory;
  • the modification unit is further configured to complete the modification of the node data in the DRAM memory according to the data to be replaced carried in the data modification instruction, and trigger the setting unit to set a dirty flag on the modified node data .
  • it also includes a migration unit
  • the migration unit is configured to transfer the data mapped to the DRAM memory with the dirty flag set to the DCPMM memory according to a preset cycle time.
  • the embodiment of the present invention also provides a B+ tree access device, including:
  • Memory used to store computer programs
  • the processor is configured to execute the computer program to implement the steps of the B+ tree access method described in any one of the above.
  • the embodiment of the present invention also provides a computer-readable storage medium, the computer-readable storage medium stores a computer program, and when the computer program is executed by a processor, the access to the B+ tree as described in any one of the above is realized Method steps.
  • the data of the number of layers in the B+ tree greater than or equal to the preset threshold is stored in the preset storage area.
  • each data read needs to be accessed from the bottom data, so the bottom data is accessed more times.
  • the access efficiency of the underlying data is improved.
  • data other than the underlying data is accessed relatively few times.
  • other data can be stored in storage space other than DRAM memory, which improves the utilization of DRAM memory resources. Rate, and can ensure the read and write efficiency of the B+ tree.
  • FIG. 1 is a flowchart of a method for accessing a B+ tree provided by an embodiment of the present invention
  • FIG. 2 is a flowchart of a method for modifying data of a B+ tree provided by an embodiment of the present invention
  • FIG. 3 is a schematic structural diagram of a B+ tree access device provided by an embodiment of the present invention.
  • FIG. 4 is a schematic diagram of the hardware structure of a B+ tree access device provided by an embodiment of the present invention.
  • FIG. 1 is a flowchart of a method for accessing a B+ tree provided by an embodiment of the present invention. The method includes:
  • S102 Store the bottom-level data of the B+ tree in the bottom-level tree file.
  • S103 Create a new target bottom-level data file, and map the target bottom-level tree file to the DRAM memory, so as to store the bottom-level data of the B+ tree into the target bottom-level tree file.
  • each data read needs to be accessed from the bottom data, so the bottom data is accessed more frequently.
  • the bottom file By storing the bottom file in the free bottom tree file mapped to the DRAM memory, it is effectively improved The access efficiency of the underlying data is improved.
  • the newly created bottom-level tree file is called the target bottom-level tree file.
  • the target bottom-level tree file For the storage system, both the newly-created target bottom-level tree file and the bottom-level tree file are used for storage. There is no substantial difference between the two files of the underlying data.
  • S104 When the number of layers of the B+ tree is greater than or equal to the preset threshold, store data with the number of layers in the B+ tree greater than or equal to the preset threshold to a preset storage area.
  • the B+ tree contains multiple levels of data.
  • the data of the B+ tree can be divided into different levels. The frequency and number of times the data of different levels are accessed are different. Therefore, the data of different levels can be stored In a different location.
  • the B+ tree can be divided into a first level, a second level, and a third level; among them, the data of the first level is used as the bottom data.
  • the frequency of accessing the bottom-level data is relatively high. Therefore, in the embodiment of the present invention, the bottom-level data is stored in a free bottom-level tree file mapped to the DRAM memory.
  • the DCPMM device in the Device DAX mode can be regarded as a DCPMM memory.
  • the data of the second level of the B+ tree can be stored in the DCPMM memory.
  • the data of the third level of the B+ tree can be stored in the preset hard disk.
  • the files from the first level to the third level of the B+ tree can be regarded as the first level
  • the fourth and fifth level files are regarded as the second level
  • the data larger than the fifth level file can be regarded as the third level. Level.
  • the data of the number of layers in the B+ tree greater than or equal to the preset threshold is stored in the preset storage area.
  • each data read needs to be accessed from the bottom data, so the bottom data is accessed more times.
  • the access efficiency of the underlying data is improved.
  • data other than the underlying data is accessed relatively few times.
  • other data can be stored in storage space other than DRAM memory, which improves the utilization of DRAM memory resources. Rate, and can ensure the read and write efficiency of the B+ tree.
  • the bottom data is accessed more frequently, so the bottom data can be stored in the DRAM memory.
  • the frequency of access to the bottom data of the B+ tree decreases, in order to improve DRAM
  • a dirty flag can be set for the underlying data stored in the DRAM memory, so that the underlying data stored in the DRAM memory can be periodically migrated to the DCPMM memory.
  • the minimum read and write granularity of the DCPMM memory can be used as the node capacity of the B+ tree.
  • the minimum internal read and write granularity of the DCPMM memory is 256 bytes. Therefore, the capacity of a B+ tree node can be set to 256 bytes, that is, a set of check protection data is generated for every 256 bytes of data.
  • the bottom-level data of the B+ tree can be stored in the bottom-level tree file according to the node capacity; the key-value pair of each node data stores the offset address of the next-level node.
  • each node can contain a 16-byte node header and up to 15 key-value pairs.
  • the node header contains information such as the node type.
  • the node types include leaf nodes and non-leaf nodes.
  • the value in the key-value pair is the RAID physical address. According to the RAID physical address, the specific data corresponding to the leaf node can be read; for non-leaf nodes, the next-level node can be stored in the key-value pair.
  • the offset address is the RAID physical address.
  • the root node When the data query instruction is obtained, the root node can be determined according to the logical address carried in the data query instruction; the leaf node can be determined according to the offset address contained in the root node; and the data corresponding to the leaf node can be read.
  • the logical address of the data volume can be carried in the data query instruction.
  • the metadata of the data volume can be found. If the memory address of the root node is protected in the metadata, the bottom tree file of the tree is in the memory. According to the offset address stored in the corresponding node in the bottom tree file, you can Find the leaf node. If the node is still not a leaf node at the third level, the offset address of the corresponding node in the third level file is read from the metadata to obtain the storage address of the fourth level file. If the node is still a non-leaf node, then continue to access the 5th layer node.
  • the layer 5 node If the layer 5 node is still not a leaf node, read the third-level file into the memory and continue searching until it reaches the leaf node. According to the RAID physical address stored in the key-value pair of the leaf node, it can be read to the leaf node. Corresponding specific data.
  • the data of the B+ tree is stored in different locations according to the divided levels.
  • the storage location of the data to be modified can be queried according to the storage location to modify the data in the B+ tree, as shown in the figure 2 is a flowchart of a method for modifying B+ tree data provided by an embodiment of the present invention, including:
  • S202 Modify the node data according to the data to be replaced carried in the data modification instruction, and set a dirty flag for the modified node data.
  • Node data is stored in DRAM memory, which will occupy DRAM memory resources.
  • the data with the dirty flag is migrated to the DCPMM memory.
  • S203 Determine whether there is node data matching the node identifier carried in the data modification instruction in the DCPMM memory.
  • the data of the B+ tree is stored in the DRAM memory, the DCPMM memory, and the preset hard disk according to different levels.
  • the node data that needs to be modified is stored in the preset hard disk, and S205 can be executed at this time.
  • S204 Modify the node data according to the data to be replaced carried in the data modification instruction.
  • the node data in the hard disk cannot be modified directly, when the node data to be modified is stored in the preset hard disk, the node data in the hard disk that matches the node identifier carried in the data modification instruction needs to be read to DRAM In memory.
  • the modified node data stored in the DRAM memory can be set with a dirty flag, so that the data mapped to the DRAM memory with the dirty flag can be migrated to the DCPMM according to the preset cycle time. In memory.
  • the data of the B+ tree is avoided from occupying the resources of the DRAM memory for a long time, and the processing performance of the storage system is effectively improved.
  • FIG. 3 is a schematic structural diagram of a B+ tree access device provided by an embodiment of the present invention, which includes a first judging unit 31, a first storage unit 32, a creation unit 33, and a second storage unit 34;
  • the first judging unit 31 is used for judging whether there is an idle underlying tree file mapped to the DRAM memory when the B+ tree creation instruction is obtained; if it is, trigger the first storage unit 32; if not, trigger the creation unit 33;
  • the first storage unit 32 is used to store the bottom-level data of the B+ tree to the bottom-level tree file
  • the creating unit 33 is configured to create a new target bottom-level data file and map the target bottom-level tree file to the DRAM memory, so as to store the bottom-level data of the B+ tree into the target bottom-level tree file;
  • the second storage unit 34 is configured to store data with the number of layers in the B+ tree greater than or equal to the preset threshold value in the preset storage area when the number of layers of the B+ tree is greater than or equal to the preset threshold.
  • the B+ tree corresponds to the first level, the second level, and the third level; wherein, the data of the first level is used as the bottom data;
  • the second storage unit is specifically configured to store the data of the second level of the B+ tree into the DCPMM memory; and store the data of the third level of the B+ tree into the preset hard disk.
  • it also includes as a unit;
  • the first storage unit is specifically configured to store the bottom-level data of the B+ tree in the bottom-level tree file according to the node capacity; wherein, the key-value pair of each node data stores the offset of the next-level node address.
  • it further includes a query unit, a determination unit, and a reading unit;
  • the query unit is used to determine the root node according to the logical address carried in the data query instruction when the data query instruction is obtained;
  • the determining unit is used to determine the leaf node according to the offset address contained in the root node;
  • the reading unit is used to read the data corresponding to the leaf node.
  • it further includes a second judgment unit, a modification unit, a setting unit, a third judgment unit, and a reading unit;
  • the second judging unit is used for judging whether there is node data matching the node identification carried in the data modification instruction in the DRAM memory when the data modification instruction is obtained; if yes, trigger the modification unit; if not, trigger the third Judgment unit
  • the modification unit is used to modify the node data according to the data to be replaced carried in the data modification instruction,
  • the setting unit is used to set the dirty flag on the modified node data
  • the third judgment unit judges whether there is node data matching the node identifier carried in the data modification instruction in the DCPMM memory;
  • the modification unit is also used to modify the node data according to the data to be replaced carried in the data modification instruction when there is node data in the DCPMM memory that matches the node identifier carried in the data modification instruction;
  • the reading unit is used to read the node data matching the node identification carried in the data modification instruction from the hard disk to the DRAM when there is no node data matching the node identification carried in the data modification instruction in the DCPMM memory In memory
  • the modification unit is also used to complete the modification of the node data in the DRAM memory according to the data to be replaced carried in the data modification instruction, and trigger the setting unit to set a dirty flag on the modified node data.
  • it also includes a migration unit
  • the migration unit is used to transfer the data mapped to the DRAM memory with the dirty flag set to the DCPMM memory according to the preset cycle time.
  • the data of the number of layers in the B+ tree greater than or equal to the preset threshold is stored in the preset storage area.
  • each data read needs to be accessed from the bottom data, so the bottom data is accessed more times.
  • the access efficiency of the underlying data is improved.
  • data other than the underlying data is accessed relatively few times.
  • other data can be stored in storage space other than DRAM memory, which improves the utilization of DRAM memory resources. Rate, and can ensure the read and write efficiency of the B+ tree.
  • FIG. 4 is a schematic diagram of the hardware structure of a B+ tree access device 40 provided by an embodiment of the present invention, including:
  • the memory 41 is used to store computer programs
  • the processor 42 is configured to execute the computer program to implement the steps of the B+ tree access method described in any of the foregoing embodiments.
  • the embodiment of the present invention also provides a computer-readable storage medium, the computer-readable storage medium stores a computer program, and when the computer program is executed by a processor, the storage of the B+ tree as described in any of the above-mentioned embodiments is realized. Take the steps of the method.
  • the steps of the method or algorithm described in combination with the embodiments disclosed herein can be directly implemented by hardware, a software module executed by a processor, or a combination of the two.
  • the software module can be placed in random access memory (RAM), internal memory, read-only memory (ROM), electrically programmable ROM, electrically erasable programmable ROM, registers, hard disks, removable disks, CD-ROMs, or all areas in the technical field. Any other known storage media.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

一种B+树的存取方法、装置和介质，获取到B+树创建指令时，判断是否存在映射到DRAM内存的空闲的底层树文件；若是，则将B+树的底层数据存储至底层树文件。若否，则新建一个目标底层数文件，并将目标底层树文件映射至DRAM内存，以便于将B+树的底层数据存储至目标底层树文件中。当B+树的层数大于或等于预设阈值时，则将B+树中层数大于或等于预设阈值的数据存储至预先设定的存储区域。基于B+树的数据结构，每次数据的读取都需要从底层数据访问，通过将底层文件存储在映射到DRAM内存的空闲的底层树文件，有效的提升了底层数据的访问效率。将其它数据存储在除DRAM内存外的存储空间中，提升了DRAM内存资源的利用率。

Description

一种B+树的存取方法、装置和计算机可读存储介质
本申请要求于2020年02月14日提交中国专利局、申请号为202010093601.7、发明名称为“一种B+树的存取方法、装置和计算机可读存储介质”的中国专利申请的优先权，其全部内容通过引用结合在本申请中。
技术领域
本发明涉及数据存储技术领域，特别是涉及一种B+树的存取方法、装置和计算机可读存储介质。
背景技术
在全闪存阵列存储系统中，由于其结构的特殊性，大量采用B+树结构。例如，全闪存阵列普遍采用自动精简的容量分配方式(thin provisioning)，其卷的逻辑地址与卷在磁盘阵列(Redundant Arrays of Independent Disks，RAID)上的物理地址不再是线性对应关系，而变成了近似随机映射的关系。为了管理这种映射关系，采用B+树来保存从卷逻辑地址到物理地址的映射，并且采用B+树来保存物理地址到逻辑地址的逆映射。全闪存阵列的重删功能，采用B+树来保存数据块HASH值到物理地址的映射。
动态随机存取存储器(Dynamic Random Access Memory，DRAM)是一种较为常见的系统内存。由于DRAM内存是较为昂贵的部件，因此存储系统中通常只配置较少数量的DRAM内存以降低成本。现有技术中，B+树的数据通常保存在固态硬盘(Solid State Drives，SSD)中。SSD盘中的数据必须读到内存中才能进行读写访问，而SSD读写的IO路径比较长，速度慢。B+树结构的频繁的读入及换出内存，会带来很大的CPU开销。
可见，如何提升B+树的读写效率，是本领域技术人员需要解决的问题。
发明内容
本发明实施例的目的是提供一种B+树的存取方法、装置和计算机可读 存储介质，可以提升B+树的读写效率。
为解决上述技术问题，本发明实施例提供一种B+树的存取方法，包括：
获取到B+树创建指令时，判断是否存在映射到DRAM内存的空闲的底层树文件；
若是，则将所述B+树的底层数据存储至所述底层树文件；
若否，则新建一个目标底层数文件，并将所述目标底层树文件映射至DRAM内存，以便于将所述B+树的底层数据存储至所述目标底层树文件中；
当所述B+树的层数大于或等于预设阈值时，则将所述B+树中层数大于或等于所述预设阈值的数据存储至预先设定的存储区域。
可选地，所述B+树对应有第一层级、第二层级和第三层级；其中，第一层级的数据作为底层数据；
相应的，所述当所述B+树的层数大于或等于预设阈值时，则将所述B+树中大于或等于所述预设阈值的数据存储至预先设定的存储区域包括：
将所述B+树的第二层级的数据存储至DCPMM内存中；
将所述B+树的第三层级的数据存储至预设的硬盘中。
可选地，在所述获取到B+树创建指令时，判断是否存在映射到内存的底层树文件之前还包括：
将所述DCPMM内存的最小读写粒度作为所述B+树的节点容量。
可选地，所述将所述B+树的底层数据存储至所述底层树文件包括：
将所述B+树的底层数据按照所述节点容量向所述底层树文件中存储各节点数据；其中，每个节点数据的键值对中存储有下一层级节点的偏移地址。
可选地，还包括：
当获取到数据查询指令时，依据所述数据查询指令中携带的逻辑地址，确定出根节点；
根据所述根节点中包含的偏移地址，确定出叶子节点；并读取所述叶子节点对应的数据。
可选地，还包括：
当获取到数据修改指令时，判断所述DRAM内存中是否存在与所述数据修改指令中携带的节点标识相匹配的节点数据；
若是，则依据所述数据修改指令中携带的待替换数据，对所述节点数据进行修改，并对修改后的节点数据设置脏标志；
若否，则判断所述DCPMM内存中是否存在与所述数据修改指令中携带的节点标识相匹配的节点数据；
当所述DCPMM内存中存在与所述数据修改指令中携带的节点标识相匹配的节点数据时，则依据所述数据修改指令中携带的待替换数据，对所述节点数据进行修改；
当所述DCPMM内存中不存在与所述数据修改指令中携带的节点标识相匹配的节点数据时，则将所述硬盘中与所述数据修改指令中携带的节点标识相匹配的节点数据读取至所述DRAM内存中；依据所述数据修改指令中携带的待替换数据，在所述DRAM内存中完成对所述节点数据的修改，并对修改后的节点数据设置脏标志。
可选地，在所述将所述B+树的底层数据存储至所述底层树文件之后还包括：
按照预设的周期时间将映射至DRAM内存中设置有脏标志的数据迁移至所述DCPMM内存中。
本发明实施例还提供了一种B+树的存取装置，包括第一判断单元、第一存储单元、创建单元和第二存储单元；
所述第一判断单元，用于获取到B+树创建指令时，判断是否存在映射到DRAM内存的空闲的底层树文件；若是，则触发所述第一存储单元；若否，则触发所述创建单元；
所述第一存储单元，用于将所述B+树的底层数据存储至所述底层树文件；
所述创建单元，用于新建一个目标底层数文件，并将所述目标底层树文件映射至DRAM内存，以便于将所述B+树的底层数据存储至所述目标底层树文件中；
所述第二存储单元，用于当所述B+树的层数大于或等于预设阈值时， 则将所述B+树中层数大于或等于所述预设阈值的数据存储至预先设定的存储区域。
可选地，所述B+树对应有第一层级、第二层级和第三层级；其中，第一层级的数据作为底层数据；
相应的，所述第二存储单元具体用于将所述B+树的第二层级的数据存储至DCPMM内存中；将所述B+树的第三层级的数据存储至预设的硬盘中。
可选地，还包括作为单元；
所述作为单元，用于将所述DCPMM内存的最小读写粒度作为所述B+树的节点容量。
可选地，所述第一存储单元具体用于将所述B+树的底层数据按照所述节点容量向所述底层树文件中存储各节点数据；其中，每个节点数据的键值对中存储有下一层级节点的偏移地址。
可选地，还包括查询单元、确定单元和读取单元；
所述查询单元，用于当获取到数据查询指令时，依据所述数据查询指令中携带的逻辑地址，确定出根节点；
所述确定单元，用于根据所述根节点中包含的偏移地址，确定出叶子节点；
所述读取单元，用于读取所述叶子节点对应的数据。
可选地，还包括第二判断单元、修改单元、设置单元、第三判断单元和读取单元；
所述第二判断单元，用于当获取到数据修改指令时，判断所述DRAM内存中是否存在与所述数据修改指令中携带的节点标识相匹配的节点数据；若是，则触发所述修改单元；若否，则触发所述第三判断单元；
所述修改单元，用于依据所述数据修改指令中携带的待替换数据，对所述节点数据进行修改，
所述设置单元，用于对修改后的节点数据设置脏标志；
所述第三判断单元判断所述DCPMM内存中是否存在与所述数据修改指令中携带的节点标识相匹配的节点数据；
所述修改单元还用于当所述DCPMM内存中存在与所述数据修改指令中携带的节点标识相匹配的节点数据时，则依据所述数据修改指令中携带的待替换数据，对所述节点数据进行修改；
所述读取单元，用于当所述DCPMM内存中不存在与所述数据修改指令中携带的节点标识相匹配的节点数据时，则将所述硬盘中与所述数据修改指令中携带的节点标识相匹配的节点数据读取至所述DRAM内存中；
所述修改单元还用于依据所述数据修改指令中携带的待替换数据，在所述DRAM内存中完成对所述节点数据的修改，并触发所述设置单元对修改后的节点数据设置脏标志。
可选地，还包括迁移单元；
所述迁移单元，用于按照预设的周期时间将映射至DRAM内存中设置有脏标志的数据转移至所述DCPMM内存中。
本发明实施例还提供了一种B+树的存取装置，包括：
存储器，用于存储计算机程序；
处理器，用于执行所述计算机程序以实现如上述任意一项所述B+树的存取方法的步骤。
本发明实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如上述任意一项所述B+树的存取方法的步骤。
由上述技术方案可以看出，获取到B+树创建指令时，判断是否存在映射到DRAM内存的空闲的底层树文件；当存在映射到DRAM内存的空闲的底层树文件时，则可以直接将B+树的底层数据存储至底层树文件。当不存在映射到DRAM内存的空闲的底层树文件时，则需要新建一个目标底层数文件，并将目标底层树文件映射至DRAM内存，以便于将B+树的底层数据存储至目标底层树文件中。当B+树的层数大于或等于预设阈值时，则将B+树中层数大于或等于预设阈值的数据存储至预先设定的存储区域。基于B+树的数据结构，每次数据的读取都需要从底层数据访问，因此底层数据被访问的次数较多，通过将底层文件存储在映射到DRAM内存的空闲的底层树文件，有效的提升了底层数据的访问效率。而B+树中除底层数据外 的其它数据被访问的次数相对较少，为了降低对DRAM内存的占用，可以将其它数据存储在除DRAM内存外的存储空间中，既提升了DRAM内存资源的利用率，又可以保证B+树的读写效率。
附图说明
为了更清楚地说明本发明实施例，下面将对实施例中所需要使用的附图做简单的介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1为本发明实施例提供的一种B+树的存取方法的流程图；
图2为本发明实施例提供的一种B+树的数据修改方法的流程图；
图3为本发明实施例提供的一种B+树的存取装置的结构示意图；
图4为本发明实施例提供的一种B+树的存取装置的硬件结构示意图。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下，所获得的所有其他实施例，都属于本发明保护范围。
为了使本技术领域的人员更好地理解本发明方案，下面结合附图和具体实施方式对本发明作进一步的详细说明。
接下来，详细介绍本发明实施例所提供的一种B+树的存取方法。图1为本发明实施例提供的一种B+树的存取方法的流程图，该方法包括：
S101：获取到B+树创建指令时，判断是否存在映射到DRAM内存的空闲的底层树文件。
当存在映射到DRAM内存的空闲的底层树文件时，则说明DRAM内存中存在可以用于存储B+树的文件，此时可以执行S102。
当不存在映射到DRAM内存的空闲的底层树文件时，则说明当前的DRAM内存中不存在用于存储B+树的文件，此时可以执行S103。
S102：将B+树的底层数据存储至底层树文件。
S103：新建一个目标底层数文件，并将目标底层树文件映射至DRAM内存，以便于将B+树的底层数据存储至目标底层树文件中。
基于B+树的数据结构，每次数据的读取都需要从底层数据访问，因此底层数据被访问的次数较频繁，通过将底层文件存储在映射到DRAM内存的空闲的底层树文件，有效的提升了底层数据的访问效率。
需要说明的是，为了便于区分，在本发明实施例中，将新建的底层树文件称作目标底层树文件，对于存储系统而言，新建的目标底层树文件与底层树文件均是用于存储底层数据的文件，两者并不存在实质性区别。
S104：当B+树的层数大于或等于预设阈值时，则将B+树中层数大于或等于预设阈值的数据存储至预先设定的存储区域。
B+树包含有多层数据，在本发明实施例中，可以将B+树的数据进行不同层级的划分，不同层级的数据被访问的频率和次数有所差异，因此，可以将不同层级的数据存储在不同的位置。
在具体实现中，可以将B+树划分为第一层级、第二层级和第三层级；其中，第一层级的数据作为底层数据。
在B+树创建初期，底层数据被访问的频率较高，因此，在本发明实施例中，将底层数据存储在映射到DRAM内存的空闲的底层树文件中。
考虑到数据中心级持久性内存模块(DC Persistent Memory Module，DCPMM)在Device DAX模式下可以实现数据的直接存取，无需依赖于DRAM内存，Device DAX模式下的DCPMM器件可以看作是DCPMM内存。在本发明实施例中，可以将B+树的第二层级的数据存储至DCPMM内存中。
为了精确的控制DCPMM的使用，避免DCPMM资源的浪费，可以将B+树的第三层级的数据存储至预设的硬盘中。
在实际应用中，可以将B+树的第一层文件至第三层文件作为第一层级，将第四层文件和第五层文件作为第二层级，将大于第五层文件的数据 作为第三层级。
由上述技术方案可以看出，获取到B+树创建指令时，判断是否存在映射到DRAM内存的空闲的底层树文件；当存在映射到DRAM内存的空闲的底层树文件时，则可以直接将B+树的底层数据存储至底层树文件。当不存在映射到DRAM内存的空闲的底层树文件时，则需要新建一个目标底层数文件，并将目标底层树文件映射至DRAM内存，以便于将B+树的底层数据存储至目标底层树文件中。当B+树的层数大于或等于预设阈值时，则将B+树中层数大于或等于预设阈值的数据存储至预先设定的存储区域。基于B+树的数据结构，每次数据的读取都需要从底层数据访问，因此底层数据被访问的次数较多，通过将底层文件存储在映射到DRAM内存的空闲的底层树文件，有效的提升了底层数据的访问效率。而B+树中除底层数据外的其它数据被访问的次数相对较少，为了降低对DRAM内存的占用，可以将其它数据存储在除DRAM内存外的存储空间中，既提升了DRAM内存资源的利用率，又可以保证B+树的读写效率。
在B+树的创建初期，底层数据被访问的次数较为频繁，因此可以将底层数据存储在DRAM内存中，随着存储时间的增长，B+树的底层数据被访问的频率有所下降，为了提升DRAM内存的利用率，因此，在具体实现中，可以对存储于DRAM内存中的底层数据设置脏标识，以便于可以将存储在DRAM内存中的底层数据周期性迁移至DCPMM内存中。
为了提升数据的读取效率，在具体实现中，可以将DCPMM内存的最小读写粒度作为B+树的节点容量。DCPMM内存的内部最小读写粒度为256字节，因此，可以将一个B+树节点的容量设置为256字节，也即每256字节数据产生一组校验保护数据。
在本发明实施例中，可以将B+树的底层数据按照节点容量向底层树文件中存储各节点数据；其中，每个节点数据的键值对中存储有下一层级节点的偏移地址。
在实际应用中，每个节点可以包含一个16字节的节点头和最多15个键值对。节点头包含节点类型等信息。其中，节点类型包括叶子节点和非 叶子节点。对于叶子节点，其键值对中的值为RAID物理地址，依据该RAID物理地址，可以读取到叶子节点所对应的具体数据；对于非叶子节点，其键值对中可以存储下一层级节点的偏移地址。
当获取到数据查询指令时，可以依据数据查询指令中携带的逻辑地址，确定出根节点；根据根节点中包含的偏移地址，确定出叶子节点；并读取叶子节点对应的数据。
举例说明，当需要查询B+树的数据时，可以在数据查询指令中携带数据卷的逻辑地址。根据该逻辑地址，可以找到这个数据卷的元数据，如果元数据中保护根节点内存地址，则该树的底层树文件在内存中，依据底层树文件中相应节点中存储的偏移地址，可以查找叶子节点，如果走到第3层节点仍然不是叶子节点，则从元数据读取第3层文件中相应节点的偏移地址，从而得到第4层文件的存储地址。如果该节点仍然为非叶子节点，则继续进行第5层节点的访问。如果5层节点仍然不是叶子节点，则读入第三层级的文件到内存，继续查找，直到到达叶子节点为止，根据叶子节点的键值对存储的RAID物理地址，便可以读取到叶子节点所对应的具体数据。
B+树的数据按照划分的层级存储在不同的位置，当需要修改B+树的数据时，可以按照存储位置查询所需修改的数据所在的存储位置，以实现对B+树中数据的修改，如图2所示为本发明实施例提供的一种B+树的数据修改方法的流程图，包括：
S201：当获取到数据修改指令时，判断DRAM内存中是否存在与数据修改指令中携带的节点标识相匹配的节点数据。
当DRAM内存中存在与数据修改指令中携带的节点标识相匹配的节点数据，则执行S202。
当DRAM内存中不存在与数据修改指令中携带的节点标识相匹配的节点数据，则需要进一步确定所需修改的节点数据所在的位置，此时可以执行S203。
S202：依据数据修改指令中携带的待替换数据，对节点数据进行修改， 并对修改后的节点数据设置脏标志。
节点数据存储在DRAM内存中，会占用DRAM内存的资源，为了提升DRAM资源的利用率，可以对修改后的节点数据设置脏标志，以便于后续可以按照预设的周期时间将映射至DRAM内存中设置有脏标志的数据迁移至DCPMM内存中。
S203：判断DCPMM内存中是否存在与数据修改指令中携带的节点标识相匹配的节点数据。
当DCPMM内存中存在与数据修改指令中携带的节点标识相匹配的节点数据，则执行S204。
在本发明实施例中，B+树的数据按照不同的层级会分别存储在DRAM内存、DCPMM内存以及预设的硬盘中，当DRAM内存中不存在与数据修改指令中携带的节点标识相匹配的节点数据，并且DCPMM内存中也不存在与数据修改指令中携带的节点标识相匹配的节点数据，则说明所需修改的节点数据存储在预设的硬盘中，此时可以执行S205。
S204：依据数据修改指令中携带的待替换数据，对节点数据进行修改。
S205：将硬盘中与数据修改指令中携带的节点标识相匹配的节点数据读取至DRAM内存中。
由于硬盘中的数据无法直接进行修改，因此，当所需修改的节点数据存储在预设的硬盘中时，需要将硬盘中与数据修改指令中携带的节点标识相匹配的节点数据读取至DRAM内存中。
S206：依据数据修改指令中携带的待替换数据，在DRAM内存中完成对节点数据的修改，并对修改后的节点数据设置脏标志。
当所需修改的节点数据存储在DRAM内存中或者硬盘中时，修改后的节点数据会存储在DRAM内存中，由于DRAM内存资源有限，为了避免修改后的节点数据长时间占用DRAM内存的资源，因此在本发明实施例中，可以将存储在DRAM内存中的修改后的节点数据设置脏标识，以便于后续可以按照预设的周期时间将映射至DRAM内存中设置有脏标志的数据迁移至DCPMM内存中。
通过定期对存储在DRAM内存中数据迁移，避免了B+树的数据长时 间占用DRAM内存的资源，有效的提升了存储系统的处理性能。
图3为本发明实施例提供的一种B+树的存取装置的结构示意图，包括第一判断单元31、第一存储单元32、创建单元33和第二存储单元34；
第一判断单元31，用于获取到B+树创建指令时，判断是否存在映射到DRAM内存的空闲的底层树文件；若是，则触发第一存储单元32；若否，则触发创建单元33；
第一存储单元32，用于将B+树的底层数据存储至底层树文件；
创建单元33，用于新建一个目标底层数文件，并将目标底层树文件映射至DRAM内存，以便于将B+树的底层数据存储至目标底层树文件中；
第二存储单元34，用于当B+树的层数大于或等于预设阈值时，则将B+树中层数大于或等于预设阈值的数据存储至预先设定的存储区域。
可选地，B+树对应有第一层级、第二层级和第三层级；其中，第一层级的数据作为底层数据；
相应的，第二存储单元具体用于将B+树的第二层级的数据存储至DCPMM内存中；将B+树的第三层级的数据存储至预设的硬盘中。
可选地，还包括作为单元；
作为单元，用于将DCPMM内存的最小读写粒度作为B+树的节点容量。
可选地，第一存储单元具体用于将B+树的底层数据按照节点容量向底层树文件中存储各节点数据；其中，每个节点数据的键值对中存储有下一层级节点的偏移地址。
可选地，还包括查询单元、确定单元和读取单元；
查询单元，用于当获取到数据查询指令时，依据数据查询指令中携带的逻辑地址，确定出根节点；
确定单元，用于根据根节点中包含的偏移地址，确定出叶子节点；
读取单元，用于读取叶子节点对应的数据。
可选地，还包括第二判断单元、修改单元、设置单元、第三判断单元和读取单元；
第二判断单元，用于当获取到数据修改指令时，判断DRAM内存中是否存在与数据修改指令中携带的节点标识相匹配的节点数据；若是，则触发修改单元；若否，则触发第三判断单元；
修改单元，用于依据数据修改指令中携带的待替换数据，对节点数据进行修改，
设置单元，用于对修改后的节点数据设置脏标志；
第三判断单元判断DCPMM内存中是否存在与数据修改指令中携带的节点标识相匹配的节点数据；
修改单元还用于当DCPMM内存中存在与数据修改指令中携带的节点标识相匹配的节点数据时，则依据数据修改指令中携带的待替换数据，对节点数据进行修改；
读取单元，用于当DCPMM内存中不存在与数据修改指令中携带的节点标识相匹配的节点数据时，则将硬盘中与数据修改指令中携带的节点标识相匹配的节点数据读取至DRAM内存中；
修改单元还用于依据数据修改指令中携带的待替换数据，在DRAM内存中完成对节点数据的修改，并触发设置单元对修改后的节点数据设置脏标志。
可选地，还包括迁移单元；
迁移单元，用于按照预设的周期时间将映射至DRAM内存中设置有脏标志的数据转移至DCPMM内存中。
图3所对应实施例中特征的说明可以参见图1和图2所对应实施例的相关说明，这里不再一一赘述。
由上述技术方案可以看出，获取到B+树创建指令时，判断是否存在映射到DRAM内存的空闲的底层树文件；当存在映射到DRAM内存的空闲的底层树文件时，则可以直接将B+树的底层数据存储至底层树文件。当不存在映射到DRAM内存的空闲的底层树文件时，则需要新建一个目标底层数文件，并将目标底层树文件映射至DRAM内存，以便于将B+树的底层数据存储至目标底层树文件中。当B+树的层数大于或等于预设阈值时，则将B+树中层数大于或等于预设阈值的数据存储至预先设定的存储区域。基 于B+树的数据结构，每次数据的读取都需要从底层数据访问，因此底层数据被访问的次数较多，通过将底层文件存储在映射到DRAM内存的空闲的底层树文件，有效的提升了底层数据的访问效率。而B+树中除底层数据外的其它数据被访问的次数相对较少，为了降低对DRAM内存的占用，可以将其它数据存储在除DRAM内存外的存储空间中，既提升了DRAM内存资源的利用率，又可以保证B+树的读写效率。
图4为本发明实施例提供的一种B+树的存取装置40的硬件结构示意图，包括：
存储器41，用于存储计算机程序；
处理器42，用于执行所述计算机程序以实现如上述任意实施例所述的B+树的存取方法的步骤。
本发明实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如上述任意实施例所述的B+树的存取方法的步骤。
以上对本发明实施例所提供的一种B+树的存取方法、装置和计算机可读存储介质进行了详细介绍。说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以对本发明进行若干改进和修饰，这些改进和修饰也落入本发明权利要求的保护范围内。
专业人员还可以进一步意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。
结合本文中所公开的实施例描述的方法或算法的步骤可以直接用硬件、处理器执行的软件模块，或者二者的结合来实施。软件模块可以置于随机存储器(RAM)、内存、只读存储器(ROM)、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD-ROM、或技术领域内所公知的任意其它形式的存储介质中。

Claims (10)

  1. 一种B+树的存取方法，其特征在于，包括：
    获取到B+树创建指令时，判断是否存在映射到DRAM内存的空闲的底层树文件；
    若是，则将所述B+树的底层数据存储至所述底层树文件；
    若否，则新建一个目标底层数文件，并将所述目标底层树文件映射至DRAM内存，以便于将所述B+树的底层数据存储至所述目标底层树文件中；
    当所述B+树的层数大于或等于预设阈值时，则将所述B+树中层数大于或等于所述预设阈值的数据存储至预先设定的存储区域。
  2. 根据权利要求1所述的方法，其特征在于，所述B+树对应有第一层级、第二层级和第三层级；其中，第一层级的数据作为底层数据；
    相应的，所述当所述B+树的层数大于或等于预设阈值时，则将所述B+树中大于或等于所述预设阈值的数据存储至预先设定的存储区域包括：
    将所述B+树的第二层级的数据存储至DCPMM内存中；
    将所述B+树的第三层级的数据存储至预设的硬盘中。
  3. 根据权利要求2所述的方法，其特征在于，在所述获取到B+树创建指令时，判断是否存在映射到内存的底层树文件之前还包括：
    将所述DCPMM内存的最小读写粒度作为所述B+树的节点容量。
  4. 根据权利要求3所述的方法，其特征在于，所述将所述B+树的底层数据存储至所述底层树文件包括：
    将所述B+树的底层数据按照所述节点容量向所述底层树文件中存储各节点数据；其中，每个节点数据的键值对中存储有下一层级节点的偏移地址。
  5. 根据权利要求4所述的方法，其特征在于，还包括：
    当获取到数据查询指令时，依据所述数据查询指令中携带的逻辑地址，确定出根节点；
    根据所述根节点中包含的偏移地址，确定出叶子节点；并读取所述叶子节点对应的数据。
  6. 根据权利要求2所述的方法，其特征在于，还包括：
    当获取到数据修改指令时，判断所述DRAM内存中是否存在与所述数据修改指令中携带的节点标识相匹配的节点数据；
    若是，则依据所述数据修改指令中携带的待替换数据，对所述节点数据进行修改，并对修改后的节点数据设置脏标志；
    若否，则判断所述DCPMM内存中是否存在与所述数据修改指令中携带的节点标识相匹配的节点数据；
    当所述DCPMM内存中存在与所述数据修改指令中携带的节点标识相匹配的节点数据时，则依据所述数据修改指令中携带的待替换数据，对所述节点数据进行修改；
    当所述DCPMM内存中不存在与所述数据修改指令中携带的节点标识相匹配的节点数据时，则将所述硬盘中与所述数据修改指令中携带的节点标识相匹配的节点数据读取至所述DRAM内存中；依据所述数据修改指令中携带的待替换数据，在所述DRAM内存中完成对所述节点数据的修改，并对修改后的节点数据设置脏标志。
  7. 根据权利要求6所述的方法，其特征在于，在所述将所述B+树的底层数据存储至所述底层树文件之后还包括：
    按照预设的周期时间将映射至DRAM内存中设置有脏标志的数据迁移至所述DCPMM内存中。
  8. 一种B+树的存取装置，其特征在于，包括第一判断单元、第一存储单元、创建单元和第二存储单元；
    所述第一判断单元，用于获取到B+树创建指令时，判断是否存在映射到DRAM内存的空闲的底层树文件；若是，则触发所述第一存储单元；若否，则触发所述创建单元；
    所述第一存储单元，用于将所述B+树的底层数据存储至所述底层树文件；
    所述创建单元，用于新建一个目标底层数文件，并将所述目标底层树文件映射至DRAM内存，以便于将所述B+树的底层数据存储至所述目标底层树文件中；
    所述第二存储单元，用于当所述B+树的层数大于或等于预设阈值时，则将所述B+树中层数大于或等于所述预设阈值的数据存储至预先设定的存储区域。
  9. 一种B+树的存取装置，其特征在于，包括：
    存储器，用于存储计算机程序；
    处理器，用于执行所述计算机程序以实现如权利要求1至7任意一项所述B+树的存取方法的步骤。
  10. 一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如权利要求1至7任意一项所述B+树的存取方法的步骤。
PCT/CN2020/117331 2020-02-14 2020-09-24 一种b+树的存取方法、装置和计算机可读存储介质 Ceased WO2021159711A1 (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
US17/799,878 US11762827B2 (en) 2020-02-14 2020-09-24 B-plus tree access method and apparatus, and computer-readable storage medium
EP20919043.8A EP4105770B1 (en) 2020-02-14 2020-09-24 B+ tree access method and apparatus, and computer-readable storage medium

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN202010093601.7 2020-02-14
CN202010093601.7A CN111309258B (zh) 2020-02-14 2020-02-14 一种b+树的存取方法、装置和计算机可读存储介质

Publications (1)

Publication Number Publication Date
WO2021159711A1 true WO2021159711A1 (zh) 2021-08-19

Family

ID=71158329

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2020/117331 Ceased WO2021159711A1 (zh) 2020-02-14 2020-09-24 一种b+树的存取方法、装置和计算机可读存储介质

Country Status (4)

Country Link
US (1) US11762827B2 (zh)
EP (1) EP4105770B1 (zh)
CN (1) CN111309258B (zh)
WO (1) WO2021159711A1 (zh)

Families Citing this family (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111309258B (zh) * 2020-02-14 2021-10-15 苏州浪潮智能科技有限公司 一种b+树的存取方法、装置和计算机可读存储介质
US11983438B2 (en) * 2021-02-09 2024-05-14 Nutanix, Inc. Technique for improving operations log indexing
CN113392040B (zh) * 2021-06-23 2023-03-21 锐捷网络股份有限公司 一种地址映射方法、装置、设备
CN113703873B (zh) * 2021-09-03 2025-06-06 腾讯科技（深圳）有限公司 客户端的冷启动方法、装置、介质、设备和程序产品
CN113835643B (zh) * 2021-11-23 2022-03-08 苏州浪潮智能科技有限公司 数据存储方法、装置、电子设备及可读存储介质
CN119226284A (zh) * 2023-06-29 2024-12-31 中兴通讯股份有限公司 远端索引节点的确定方法、装置、设备及介质
CN116700935B (zh) * 2023-08-04 2023-11-03 苏州浪潮智能科技有限公司 一种内存数据迁移方法、装置、电子设备及存储介质
CN117194739B (zh) * 2023-09-12 2024-04-19 北京云枢创新软件技术有限公司 基于命中状态查找层次树节点的方法、电子设备和介质
CN120215825B (zh) * 2025-03-10 2026-01-06 贵州大学 一种基于zns ssd的冷热数据动态放置的b+树索引构建方法

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001350635A (ja) * 2000-06-07 2001-12-21 Nec Corp 電文一括処理システムの起動スケジューリングシステム及び起動スケジューリング方法
CN104899297A (zh) * 2015-06-08 2015-09-09 南京航空航天大学 具有存储感知的混合索引结构
CN108733678A (zh) * 2017-04-14 2018-11-02 华为技术有限公司 一种数据搜索的方法、装置和相关设备
CN109766312A (zh) * 2019-01-07 2019-05-17 深圳大学 一种区块链存储方法、系统、装置及计算机可读存储介质
CN111309258A (zh) * 2020-02-14 2020-06-19 苏州浪潮智能科技有限公司 一种b+树的存取方法、装置和计算机可读存储介质

Family Cites Families (25)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5813000A (en) * 1994-02-15 1998-09-22 Sun Micro Systems B tree structure and method
CN100391200C (zh) * 2004-12-31 2008-05-28 华为技术有限公司 一种数据传送方法
US10152504B2 (en) * 2009-03-11 2018-12-11 Actian Netherlands B.V. Column-store database architecture utilizing positional delta tree update system and methods
CN101789028B (zh) * 2010-03-19 2012-03-21 苏州广达友讯技术有限公司 地理位置搜索引擎及其构建方法
US9483356B2 (en) * 2013-03-06 2016-11-01 Quantum Corporation Heuristic journal reservations
US20150089185A1 (en) 2013-09-23 2015-03-26 International Business Machines Corporation Managing Mirror Copies without Blocking Application I/O
CA2867589A1 (en) * 2013-10-15 2015-04-15 Coho Data Inc. Systems, methods and devices for implementing data management in a distributed data storage system
US9201918B2 (en) * 2013-11-19 2015-12-01 Netapp, Inc. Dense tree volume metadata update logging and checkpointing
US9798728B2 (en) * 2014-07-24 2017-10-24 Netapp, Inc. System performing data deduplication using a dense tree data structure
US20170024140A1 (en) * 2015-07-20 2017-01-26 Samsung Electronics Co., Ltd. Storage system and method for metadata management in non-volatile memory
GB2559907A (en) * 2015-10-21 2018-08-22 Brocade Comm Systems Inc Distributed rule provisioning in an extended bridge
JP2019503598A (ja) * 2016-01-27 2019-02-07 オラクル・インターナショナル・コーポレイション 高性能コンピューティング環境においてスケーラブルなビットマップに基づくＰ＿Ｋｅｙテーブルをサポートするためのシステムおよび方法
US10789134B2 (en) * 2016-04-15 2020-09-29 Netapp, Inc. NVRAM loss handling
CN105930280B (zh) * 2016-05-27 2019-07-05 诸葛晴凤 一种面向非易失性内存的高效的页面组织和管理方法
US10558699B2 (en) * 2017-01-06 2020-02-11 Oracle International Corporation Cloud migration of file system data hierarchies
US11029862B2 (en) * 2017-04-25 2021-06-08 Netapp, Inc. Systems and methods for reducing write tax, memory usage, and trapped capacity in metadata storage
CN108804019B (zh) * 2017-04-27 2020-07-07 华为技术有限公司 一种数据存储方法及装置
US11086524B1 (en) * 2018-06-27 2021-08-10 Datadirect Networks, Inc. System and method for non-volatile memory based optimized, versioned, log-structured metadata storage with efficient data retrieval
US11423063B2 (en) * 2018-07-31 2022-08-23 Salesforce, Inc. Flattening hierarchical database records using inverted indexing
CN109407978B (zh) * 2018-09-27 2020-07-28 清华大学 高并发索引b+链表数据结构的设计与实现方法
CN109407979B (zh) * 2018-09-27 2020-07-28 清华大学 多线程持久性b+树数据结构设计与实现方法
CN110147204B (zh) * 2019-05-22 2020-03-10 苏州浪潮智能科技有限公司 一种元数据落盘方法、装置、系统及计算机可读存储介质
CN110597805B (zh) * 2019-07-24 2022-04-12 浙江大学 一种内存索引结构处理方法
WO2019228574A2 (en) * 2019-09-12 2019-12-05 Alibaba Group Holding Limited Log-structured storage systems
CN110688345A (zh) * 2019-09-26 2020-01-14 重庆大学 一种内存文件系统的多粒度结构化空间管理机制

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001350635A (ja) * 2000-06-07 2001-12-21 Nec Corp 電文一括処理システムの起動スケジューリングシステム及び起動スケジューリング方法
CN104899297A (zh) * 2015-06-08 2015-09-09 南京航空航天大学 具有存储感知的混合索引结构
CN108733678A (zh) * 2017-04-14 2018-11-02 华为技术有限公司 一种数据搜索的方法、装置和相关设备
CN109766312A (zh) * 2019-01-07 2019-05-17 深圳大学 一种区块链存储方法、系统、装置及计算机可读存储介质
CN111309258A (zh) * 2020-02-14 2020-06-19 苏州浪潮智能科技有限公司 一种b+树的存取方法、装置和计算机可读存储介质

Also Published As

Publication number Publication date
US20230078081A1 (en) 2023-03-16
EP4105770A1 (en) 2022-12-21
CN111309258B (zh) 2021-10-15
CN111309258A (zh) 2020-06-19
US11762827B2 (en) 2023-09-19
EP4105770A4 (en) 2023-07-26
EP4105770B1 (en) 2025-01-15

Similar Documents

Publication Publication Date Title
WO2021159711A1 (zh) 一种b+树的存取方法、装置和计算机可读存储介质
US12216929B2 (en) Storage system, memory management method, and management node
US12216928B2 (en) Fragment management method and fragment management apparatus
CN105718217B (zh) 一种精简配置存储池数据一致性维护的方法及装置
US9449005B2 (en) Metadata storage system and management method for cluster file system
US10565125B2 (en) Virtual block addresses
CN111125447A (zh) 一种元数据访问方法、装置、设备及可读存储介质
US8966218B2 (en) On-access predictive data allocation and reallocation system and method
US11061788B2 (en) Storage management method, electronic device, and computer program product
JP2016506585A (ja) データストレージのための方法及びシステム
WO2019015479A1 (zh) 在固态硬盘的ftl实现数据拷贝的方法、系统及固态硬盘
WO2014101420A1 (zh) 一种元数据的构建系统及其方法
US11640244B2 (en) Intelligent block deallocation verification
EP4012547B1 (en) Storage method and apparatus for key value (kv) and storage device
US10853257B1 (en) Zero detection within sub-track compression domains
EP4307129A1 (en) Method for writing data into solid-state hard disk
WO2023138264A1 (zh) 一种ssd数据管理方法及相关组件
CN115525668A (zh) Kvs的数据处理方法、装置和存储介质
CN114442934A (zh) 数据处理方法、装置及存储引擎
KR20250015818A (ko) 데이터 액세스를 위한 방법 및 장치, 전자 장치 및 저장 매체
CN119271718A (zh) 一种地址确定方法及装置
Khil et al. Hot and Cold Data Replacement Method for Hybrid Storage System

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 20919043

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

ENP Entry into the national phase

Ref document number: 2020919043

Country of ref document: EP

Effective date: 20220914