SSD映射表的实现方法、装置、可读存储介质及电子设备

摘要

本发明公开一种SSD映射表的实现方法、装置、可读存储介质及电子设备，通过接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设逻辑地址区间，根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、预设的逻辑地址对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树，再将所述待存储的映射项存储至所述目标平衡二叉树，避免了在小范围内进行随机读写时，所有映射项都存入同一颗平衡二叉树中，造成平衡二叉树层级过高的情况，均衡了各颗平衡二叉树的映射项，提高了对映射表的访问性能。

权利要求

1.一种SSD映射表的实现方法，其特征在于，包括步骤：

接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设的逻辑地址区间；

根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、所述预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树；

将所述待存储的映射项存储至所述目标平衡二叉树；

所述根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、所述预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树包括：根据所述逻辑地址对应的逻辑地址子区间确定所述逻辑地址子区间的首位的逻辑地址与末位的逻辑地址；

将所述逻辑地址子区间的首位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树；

将所述逻辑地址子区间的末位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树；

根据所述第一平衡二叉树与所述第二平衡二叉树确定存储所述逻辑地址子区间的目标平衡二叉树；

所述将所述逻辑地址子区间的首位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树包括：所述存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树标识ID为：式中，LAAfist_N表示所述逻辑地址子区间的首位的逻辑地址的标识，R表示所述预设的逻辑地址区间对应的逻辑地址个数，CNT表示所述预设平衡二叉树个数；

所述将所述逻辑地址子区间的末位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树包括：所述存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树标识ID为：式中，LAAlast_N表示所述逻辑地址子区间的末位的逻辑地址的标识。

2.根据权利要求1所述的一种SSD映射表的实现方法，其特征在于，所述接收待存储的映射项之前包括步骤：将所述预设的逻辑地址区间进行划分，得到与所述预设平衡二叉树个数对应数量的逻辑地址子区间。

3.根据权利要求1至2任一项所述的一种SSD映射表的实现方法，其特征在于，还包括步骤：判断任意两个预设的逻辑地址区间的逻辑地址子区间在对应的预设的逻辑地址区间内的相对偏移量是否相同，若是，则所述任意两个预设的逻辑地址区间的逻辑地址子区间存储在同一平衡二叉树。

4.根据权利要求1所述的一种SSD映射表的实现方法，其特征在于，还包括步骤：接收映射项查询请求，所述映射项查询请求中包括待查询的映射项；

根据所述待查询的映射项包括的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址的目标平衡二叉树；

查询所述目标平衡二叉树，确定所述逻辑地址对应的物理地址。

5.根据权利要求4所述的一种SSD映射表的实现方法，其特征在于，所述根据所述待查询的映射项包括的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址的目标平衡二叉树包括：所述存储所述逻辑地址的目标平衡二叉树标识ID为：

式中，LAAn_N表示所述逻辑地址的标识。

6.一种SSD映射表的实现装置，其特征在于，包括：

数据接收模块，用于接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设的逻辑地址区间；

数据计算模块，用于根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、所述预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树；

数据存储模块，用于将所述待存储的映射项存储至所述目标平衡二叉树；

所述根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、所述预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树包括：根据所述逻辑地址对应的逻辑地址子区间确定所述逻辑地址子区间的首位的逻辑地址与末位的逻辑地址；

将所述逻辑地址子区间的首位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树；

将所述逻辑地址子区间的末位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树；

根据所述第一平衡二叉树与所述第二平衡二叉树确定存储所述逻辑地址子区间的目标平衡二叉树；

所述将所述逻辑地址子区间的首位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树包括：所述存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树标识ID为：式中，LAAfist_N表示所述逻辑地址子区间的首位的逻辑地址的标识，R表示所述预设的逻辑地址区间对应的逻辑地址个数，CNT表示所述预设平衡二叉树个数；

所述将所述逻辑地址子区间的末位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树包括：所述存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树标识ID为：式中，LAAlast_N表示所述逻辑地址子区间的末位的逻辑地址的标识。

7.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现如权利要求1至5任一项所述的一种SSD映射表的实现方法中的各个步骤。

8.一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时实现如权利要求1至5任一项所述的一种SSD映射表的实现方法中的各个步骤。

说明书

SSD映射表的实现方法、装置、可读存储介质及电子设备

技术领域

[0001] 本发明涉及固态硬盘技术领域，尤其涉及一种SSD映射表的实现方法、装置、可读存储介质及电子设备。

背景技术

[0002] 在SSD(Solid State Disk，固态硬盘)的使用过程中，firmware(固件)为了记录主机的LBA(Logical Block Address，逻辑地址块)地址与真实的NAND(闪存)地址之间的关系，需要建立一张从逻辑地址到物理地址的映射表。在DRAM‑less(Dynamic Random Access Memory‑less，无动态随机存储器或少动态随机存储器)产品中，由于内存资源有限，映射表只会部分缓存在内存中，采用何种方式实现内存的映射表，将直接影响SSD的读写性能。

[0003] 对于映射表，若内存资源充足，那么构建一个逻辑地址到物理地址的映射数组是比较理想的实现方式。但是在DRAM‑less产品中，由于内存不足，传统的做法多是使用平衡二叉树如AVL(Adelson‑Velsky‑Landis Tree，高度平衡树)树或者红黑树等方式来存储映射表：

[0004] 法一是使用一棵平衡二叉树，当firmware产生一个entry(映射项)时，插入到该二叉树当中，该方式实现简单，但是当entry个数较多时，会造成树的层级多，而层级越多，对其进行增删查改的性能将会越慢；

[0005] 法二是基于法一进行优化，使用多棵平衡二叉树组成树的集合，每一棵树只负责存储一段逻辑地址空间，如图4所示，假设整个SSD的容量包含了10000个逻辑地址，逻辑地址从0～9999，则最多有10000个映射entry；按照逻辑地址从小到大，每1000个entry放入一颗平衡二叉树中，那么最多需要10颗平衡二叉树，每颗二叉树的层级相对于法一中的层级来说就会大幅度下降，可以提高对entry的增删查改性能。该方式在对于全盘随机写的场景下，每颗树中的entry个数大致是比较均衡的，但是若使用场景为在小范围内，例如1G空间内，那么entry将会集中在个别的树上，导致这些树的层级很高，而其他区间对应的树上则没有entry，不能充分利用多棵平衡二叉树，且对于层级很高的个别树，降低了对其进行增删查改的性能。

发明内容

[0006] 本发明所要解决的技术问题是：提供了一种SSD映射表的实现方法、装置、可读存储介质及电子设备，能够均衡各颗平衡二叉树的映射项，提高对映射表的访问性能。

[0007] 为了解决上述技术问题，本发明采用的一种技术方案为：

[0008] 一种SSD映射表的实现方法，包括步骤：

[0009] 接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设的逻辑地址区间；

[0010] 根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、所述预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树；

[0011] 将所述待存储的映射项存储至所述目标平衡二叉树。

[0012] 为了解决上述技术问题，本发明采用的另一种技术方案为：

[0013] 一种SSD映射表的实现装置，包括：

[0014] 数据接收模块，用于接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设的逻辑地址区间；

[0015] 数据计算模块，用于根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、所述预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树；

[0016] 数据存储模块，用于将所述待存储的映射项存储至所述目标平衡二叉树。

[0017] 为了解决上述技术问题，本发明采用的另一种技术方案为：

[0018] 一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述SSD映射表的实现方法中的各个步骤。

[0019] 为了解决上述技术问题，本发明采用的另一种技术方案为：

[0020] 一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现上述SSD映射表的实现方法中的各个步骤。

[0021] 本发明的有益效果在于：

[0022] 通过接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设的逻辑地址区间，根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、预设的逻辑地址对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树，再将所述待存储的映射项存储至所述目标平衡二叉树，通过哈希算法能够确定映射项要存储至哪颗平衡二叉树中，改变传统的直接按照逻辑地址分段的方式，能够将映射项均匀地存储至多个平衡二叉树中，避免了在小范围内进行随机读写时，所有映射项都存入同一颗平衡二叉树中，造成平衡二叉树层级过高的情况，均衡了各颗平衡二叉树的映射项，提高了对映射表的访问性能。

附图说明

[0023] 图1为本发明实施例的一种SSD映射表的实现方法的步骤流程图；

[0024] 图2为本发明实施例的一种SSD映射表的实现装置的结构示意图；

[0025] 图3为本发明实施例的一种电子设备的结构示意图；

[0026] 图4为本发明背景技术中直接按照逻辑地址分段的映射表实现方法示意图；

[0027] 图5为本发明实施例的SSD映射表的实现方法中1G范围内使用8颗平衡二叉树存储映射项的示意图。

具体实施方式

[0028] 为详细说明本发明的技术内容、所实现目的及效果，以下结合实施方式并配合附图予以说明。

[0029] 请参照图1，本发明实施例提供了一种SSD映射表的实现方法，包括步骤：

[0030] 接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设的逻辑地址区间；

[0031] 根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、所述预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树；

[0032] 将所述待存储的映射项存储至所述目标平衡二叉树。

[0033] 从上述描述可知，本发明的有益效果在于：通过接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设的逻辑地址区间，根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、预设的逻辑地址对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树，再将所述待存储的映射项存储至所述目标平衡二叉树，通过哈希算法能够确定映射项要存储至哪颗平衡二叉树中，改变传统的直接按照逻辑地址分段的方式，能够将映射项均匀地存储至多个平衡二叉树中，避免了在小范围内进行随机读写时，所有映射项都存入同一颗平衡二叉树中，造成平衡二叉树层级过高的情况，均衡了各颗平衡二叉树的映射项，提高了对映射表的访问性能。

[0034] 进一步地，所述接收待存储的映射项之前包括步骤：

[0035] 将所述预设的逻辑地址区间进行划分，得到与所述预设平衡二叉树个数对应数量的逻辑地址子区间。

[0036] 由上述描述可知，由于一个逻辑地址对应一个映射项，将预设的逻辑地址区间划分成与预设平衡二叉树个数对应数量的逻辑地址子区间，便于后续将映射项均匀的打散至不同的平衡二叉树中。

[0037] 进一步地，所述根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、所述预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树包括：

[0038] 根据所述逻辑地址对应的逻辑地址子区间确定所述逻辑地址子区间的首位的逻辑地址与末位的逻辑地址；

[0039] 将所述逻辑地址子区间的首位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树；

[0040] 将所述逻辑地址子区间的末位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树；

[0041] 根据所述第一平衡二叉树与所述第二平衡二叉树确定存储所述逻辑地址子区间的目标平衡二叉树。

[0042] 由上述描述可知，分别通过哈希算法计算存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树以及存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树，从而确定存储该逻辑地址子区间的目标平衡二叉树，能够将映射项分散存储至平衡二叉树中，与传统方式相比，减少了每棵平衡二叉树的映射项个数，均衡了各颗平衡二叉树的映射项。

[0043] 进一步地，所述将所述逻辑地址子区间的首位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树包括：

[0044] 所述存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树标识ID为：

[0045]

[0046] 式中，LAAfist_N表示所述逻辑地址子区间的首位的逻辑地址的标识，R表示所述预设的逻辑地址区间对应的逻辑地址个数，CNT表示所述预设平衡二叉树个数；

[0047] 所述将所述逻辑地址子区间的末位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树包括：

[0048] 所述存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树标识ID为：

[0049]

[0050] 式中，LAAlast_N表示所述逻辑地址子区间的末位的逻辑地址的标识。

[0051] 由上述描述可知，通过哈希算法计算得到存储逻辑地址子区间的首位的逻辑地址的第一平衡二叉树以及末位的逻辑地址的第二平衡二叉树，算法复杂度低，以利于数字化实现。

[0052] 进一步地，还包括步骤：

[0053] 判断任意两个预设的逻辑地址区间的逻辑地址子区间在对应的预设的逻辑地址区间内的相对偏移量是否相同，若是，则所述任意两个预设的逻辑地址区间的逻辑地址子区间存储在同一平衡二叉树。

[0054] 由上述描述可知，通过判断任意两个预设的逻辑地址区间的逻辑地址子区间在对应的预设的逻辑地址区间内的相对偏移量是否相同，能够确定任意两个预设的逻辑地址区间的逻辑地址子区间是否可以存储在同一颗平衡二叉树中，如果相同，就只需进行一次哈希计算，将其存储至同一平衡二叉树，提高了映射表的实现效率。

[0055] 进一步地，还包括步骤：

[0056] 接收映射项查询请求，所述映射项查询请求中包括待查询的映射项；

[0057] 根据所述待查询的映射项包括的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址的目标平衡二叉树；

[0058] 查询所述目标平衡二叉树，确定所述逻辑地址对应的物理地址。

[0059] 进一步地，所述根据所述待查询的映射项包括的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址的目标平衡二叉树包括：

[0060] 所述存储所述逻辑地址的目标平衡二叉树标识ID为：

[0061]

[0062] 式中，LAAn_N表示所述逻辑地址的标识。

[0063] 由上述描述可知，查询任一映射项时，根据哈希算法确定其在哪颗平衡二叉树中，确定之后对平衡二叉树进行查询操作，得到该逻辑地址对应的物理地址，能够实现对映射表的访问，提高了对映射表的访问性能。

[0064] 请参照图2，本发明另一实施例提供了一种SSD映射表的实现装置，包括：

[0065] 数据接收模块，用于接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设的逻辑地址区间；

[0066] 数据计算模块，用于根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、所述预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树；

[0067] 数据存储模块，用于将所述待存储的映射项存储至所述目标平衡二叉树。

[0068] 本发明另一实施例提供了一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述SSD映射表的实现方法中的各个步骤。

[0069] 请参照图3，本发明另一实施例提供了一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现上述SSD映射表的实现方法中的各个步骤。

[0070] 本发明上述SSD映射表的实现方法、装置、计算机可读存储介质及电子设备能够适用于任何类型的固态硬盘，比如基于闪存的固态硬盘、基于DRAM(Dynamic Random Access Memory)的固态硬盘等，以下通过具体实施方式进行说明：

[0071] 实施例一

[0072] 请参照图1、5，本发明实施例提供了一种SSD映射表的实现方法，其特征在于，包括步骤：

[0073] S0、将所述预设的逻辑地址区间进行划分，得到与所述预设平衡二叉树个数对应数量的逻辑地址子区间；

[0074] 本实施例中，主机对SSD中1G范围内进行随机读写操作，按照LAA(逻辑地址)为4k一个的粒度，1G范围内的entry(映射项)个数为256K个，即256K个LAA，所述预设平衡二叉树个数为8颗，所述预设的逻辑地址区间为1G，其对应的LAA个数为256K，如图5所示；

[0075] 其中，CNT(平衡二叉树个数)可以根据实际情况自由设置，比如根据内存的大小；RGU(逻辑地址区间)可以根据不同的使用场景进行设置，或者按照逻辑地址大小对齐；

[0076] 比如，将RGU进行划分，得到8个逻辑地址子区间，每个逻辑地址子区间中包含32K个LAA，即第一个逻辑地址子区间为LAA0～LAA32767，第二个逻辑地址子区间为LAA32768～LAA65535，第三个逻辑地址子区间为LAA65536～LAA98303，依此类推；

[0077] S1、接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设的逻辑地址区间；

[0078] 比如，接收映射项存储请求，映射项存储请求中包括待存储的entry和预设的RGU；

[0079] S2、根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、所述预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树；

[0080] 具体的，根据所述逻辑地址对应的逻辑地址子区间确定所述逻辑地址子区间的首位的逻辑地址与末位的逻辑地址；

[0081] 将所述逻辑地址子区间的首位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树；

[0082] 将所述逻辑地址子区间的末位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树；

[0083] 根据所述第一平衡二叉树与所述第二平衡二叉树确定存储所述逻辑地址子区间的目标平衡二叉树；

[0084] 其中，所述将所述逻辑地址子区间的首位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树包括：

[0085] 所述存储所述逻辑地址子区间的首位的逻辑地址的第一平衡二叉树标识ID为：

[0086]

[0087] 式中，LAAfist_N表示所述逻辑地址子区间的首位的逻辑地址的标识，R表示所述预设的逻辑地址区间对应的逻辑地址个数，CNT表示所述预设平衡二叉树个数；

[0088] 所述将所述逻辑地址子区间的末位的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树包括：

[0089] 所述存储所述逻辑地址子区间的末位的逻辑地址的第二平衡二叉树标识ID为：

[0090]

[0091] 式中，LAAlast_N表示所述逻辑地址子区间的末位的逻辑地址的标识；

[0092] S3、将所述待存储的映射项存储至所述目标平衡二叉树；

[0093] 比如，假设待存储的entry包括的LAAn对应的逻辑地址子区间是第一个逻辑地址子区间LAA0～LAA32767，确定该逻辑地址子区间的首位的逻辑地址LAA0，末位的逻辑地址LAA32767，则LAA0的标识为0，LAA32767的标识为32767；

[0094] 将LAA0的标识、RGU对应的LAA个数以及CNT基于哈希算法进行计算，那么存储LAA0的第一平衡二叉树标识ID为：

[0095]

[0096] 将LAA32767的标识、RGU对应的LAA个数以及CNT基于哈希算法进行计算，那么存储LAA32767的第二平衡二叉树标识ID为：

[0097]

[0098] 所以存储第一个逻辑地址子区间LAA0～LAA32767的目标平衡二叉树标识ID为0；

[0099] 将待存储的entry存储至标识ID为0的平衡二叉树中；

[0100] 假设LAAn对应的逻辑地址子区间是第二个逻辑地址子区间LAA32768～LAA65535，确定该逻辑地址子区间的首位的逻辑地址LAA32768，末位的逻辑地址LAA65535,则LAA32768的标识为32768，LAA65535的标识为65535；

[0101] 存储LAA32768的第一平衡二叉树标识ID为：

[0102]

[0103] 存储LAA65535的第二平衡二叉树标识ID为：

[0104]

[0105] 将待存储的entry存储至标识ID为1的平衡二叉树中，依此类推；

[0106] 本发明的映射表实现方法与法二的实现方法相比，例如对于一块256G的SSD，1G范围内随机读写，采用8棵平衡二叉树的情况下，在法二的实现方式下，32G范围的LAA都会放入同一棵树中，那么1G范围内的LAA必然都在同一棵树中，且最大会存储256K个entry；

[0107] 而使用本发明，1G范围内，这256K个entry会被均匀的存储至8棵不同的树中，那么每棵树最大只会存储32K个entry；平衡二叉树存储的entry越少，其增删查改的性能就会越高，并且当设置的平衡二叉树的个数越多的时候，两种方法下对于实现的映射表的访问性能差异越明显。

[0108] 本发明在大范围随机读写的情况下，对于最终实现的映射表的访问性能也能与法二持平。

[0109] 实施例二

[0110] 本实施例在实施例一的基础上进一步限定了如何提高映射表的实现效率，具体为：

[0111] 还包括步骤：

[0112] 判断任意两个预设的逻辑地址区间的逻辑地址子区间在对应的预设的逻辑地址区间内的相对偏移量是否相同，若是，则所述任意两个预设的逻辑地址区间的逻辑地址子区间存储在同一平衡二叉树；

[0113] 比如，接收到两个映射项存储请求，每个映射项存储请求中包括对应的RGU，判断这两个RGU的逻辑地址子区间在对应的RGU内的相对偏移量是否相同，若是，则这两个RGU的逻辑地址子区间存储在同一平衡二叉树；

[0114] 假设第一个RGU的第一个逻辑地址子区间是第0～128MB空间，那么第二个RGU的第一个逻辑地址子区间是第1024～1024+128MB空间，判断这两个逻辑地址子区间在各自的RGU内都属于第一个逻辑地址子区间，则这两个逻辑地址子区间存储在同一颗平衡二叉树中。

[0115] 实施例三

[0116] 请参照图，本实施例在实施例一或实施例二的基础上进一步限定了如何实现对映射表的访问，具体的：

[0117] 还包括步骤：

[0118] 接收映射项查询请求，所述映射项查询请求中包括待查询的映射项；

[0119] 根据所述待查询的映射项包括的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址的目标平衡二叉树；

[0120] 具体的，所述存储所述逻辑地址的目标平衡二叉树标识ID为：

[0121]

[0122] 式中，LAAn_N表示所述逻辑地址的标识；

[0123] 查询所述目标平衡二叉树，确定所述逻辑地址对应的物理地址；

[0124] 比如，接收映射项查询请求，该映射项查询请求中包括待查询的entry，待查询的entry包括LAA65545，则LAA65545的标识为65545；

[0125] 存储LAA65545的目标平衡二叉树标识ID为：

[0126]

[0127] 查询标识ID为2的平衡二叉树，确定LAA65545对应的PAA(物理地址)。

[0128] 实施例四

[0129] 请参照图2，一种SSD映射表的实现装置，包括：

[0130] 数据接收模块，用于接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设逻辑地址区间；

[0131] 数据计算模块，用于根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、所述预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的目标平衡二叉树；

[0132] 数据存储模块，用于将所述待存储的映射项存储至所述目标平衡二叉树。

[0133] 实施例五

[0134] 一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时可实现实施例一、实施例二或实施例三中SSD映射表的实现方法的各个步骤。

[0135] 实施例六

[0136] 请参照图3，一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现实施例一、实施例二或实施例三中SSD映射表的实现方法的各个步骤。

[0137] 综上所述，本发明提供的一种SSD映射表的实现方法、装置、可读存储介质及电子设备，将预设的逻辑地址区间进行划分，得到与预设平衡二叉树个数对应数量的逻辑地址子区间，便于后续将映射项均匀的打散至不同的平衡二叉树中；接收映射项存储请求，所述映射项存储请求中包括待存储的映射项和预设的逻辑地址区间；根据所述待存储的映射项包括的逻辑地址对应的逻辑地址子区间、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址子区间的平衡二叉树；将所述待存储的映射项存储至所述平衡二叉树；判断任意两个预设的逻辑地址区间的逻辑地址子区间在对应的预设的逻辑地址区间内的相对偏移量是否相同，若是，则所述任意两个预设的逻辑地址区间的逻辑地址子区间存储在同一平衡二叉树，能够提高了映射表的实现效率，当接收映射项查询请求时，根据所述待查询的映射项包括的逻辑地址、预设的逻辑地址区间对应的逻辑地址个数以及预设平衡二叉树个数基于哈希算法进行计算，确定存储所述逻辑地址的平衡二叉树；查询所述平衡二叉树，确定所述逻辑地址对应的物理地址，能够实现对映射表的访问，通过哈希算法能够确定映射项要存储至哪颗平衡二叉树中，能够将映射项均匀地存储至多个平衡二叉树中，避免了在小范围内进行随机读写时，所有映射项都存入同一颗平衡二叉树中，造成平衡二叉树层级过高的情况，均衡了各颗平衡二叉树的映射项，提高了对映射表的访问性能，且算法复杂度低，有利于数字化实现。

[0138] 在本申请所提供的上述实施例中，应该理解到，所揭露的方法、装置、计算机可读存储介质以及电子设备，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，所述模块的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个组件或模块可以结合或者可以集成到另一个装置，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或组件或模块的间接耦合或通信连接，可以是电性，机械或其它的形式。

[0139] 所述作为分离部件说明的组件可以是或者也可以不是物理上分开的，作为组件显示的部件可以是或者也可以不是物理模块，即可以位于一个地方，或者也可以分布到多个网络模块上。可以根据实际的需要选择其中的部分或者全部组件来实现本实施例方案的目的。

[0140] 另外，在本发明各个实施例中的各功能模块可以集成在一个处理模块中，也可以是各个组件单独物理存在，也可以两个或两个以上模块集成在一个模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。

[0141] 所述集成的模块如果以软件功能模块的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read‑Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

[0142] 需要说明的是，对于前述的各方法实施例，为了简便描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本发明并不受所描述的动作顺序的限制，因为依据本发明，某些步骤可以采用其它顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并不一定都是本发明所必须的。

[0143] 在上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其它实施例的相关描述。

[0144] 以上所述仅为本发明的实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等同变换，或直接或间接运用在相关的技术领域，均同理包括在本发明的专利保护范围内。