一种对象存储设备中的对象查找方法

摘要

一种对象存储设备中的对象查找方法，属于计算机存储系统的数据存取方法，解决现有对象查找方法需要多次读盘以及查找效率低的问题。本发明包括系统初始化、记录插入、记录查找和记录删除步骤，执行系统初始化步骤后，等待并根据用户不同类型的操作请求，分别进入记录插入、记录查找和记录删除步骤。本发明直接定位要搜索的哈希桶块以及直接定位要查找的记录，将现有方法的块搜索O(n)性能和记录搜索O(n)性能都提高到O(1)的性能，避免了多次读盘和平均查找长度大的不足，从而提高了对象查找速度，同时，本发明记录管理采用动态线性哈希查找方法，空间利用率高。特别适合包含大量对象的对象存储设备。

主权项

一种对象存储设备中的对象查找方法，包括：(1)系统初始化步骤：顺序进行下述过程：(1.1)根据磁盘的超级块信息，找到磁盘上索引结构体所在的磁盘块号W，根据磁盘块号W，将磁盘上索引结构体内容读到内存中；(1.2)在内存中建立映射结构体，将映射结构体的内容，设置为读取的索引结构体的I、R、N、HT；(1.3)等待用户操作，根据用户操作类型，分别转步骤(2)、(3)、(4)；(2)记录插入步骤：创建一个新对象时，进行下述过程：(2.1)从内存映射结构体中，取参数I、N、R、HT，以对象标志符为关键字，根据哈希函数，计算出哈希值，取出哈希值对应的二进制形式的低I位，并将其换算为整数，记为M，置R为R+1，将区分哈希桶是否要分裂的标志Splitflag置为0；(2.2)判断是否M＜N，是则顺序进行，否则转过程(2.10)；(2.3)将第一操作桶址D1置为HT中第M项的值，将块号为D1的磁盘块内容读到内存中的第一映射桶；(2.4)主记录号H置为所述哈希值除以J的余数，第一记录号F初始化为主记录号H；J为一个哈希桶最多存放的记录数；(2.5)在第一映射桶中取出第F个记录，判断该记录是否为空记录，是则顺序进行，否则转过程(2.7)；(2.6)将新记录添加到第一映射桶中第F个记录的位置，同时将第一映射桶的内容写回到块号为D1的磁盘块中；转过程(2.12)；(2.7)第一记录号F+1后除以J，所得余数赋予F，判断是否F＝H，是则顺序进行，否则转过程(2.5)；(2.8)判断第一映射桶是否有溢出桶，是则顺序进行，否则转过程(2.11)；(2.9)将D1置为第一映射桶的溢出桶地址，将块号为D1的磁盘块内容从磁盘读到内存中的第一映射桶，转过程(2.4)；(2.10)将M置为M‑2(I‑1)，转过程(2.3)；(2.11)在磁盘上分配块号为V的磁盘块作为第一映射桶的溢出桶，将第一映射桶的内容写回到块号为D1的磁盘块中；将第一映射桶的所有内容置为空，将新记录添加到第一映射桶中第H条记录位置，将第一操作桶址D1置为V，将第一映射桶的内容写回到块号为D1的磁盘块中；(2.12)判断是否R/N＞t，t为给定的阈值，是则顺序进行，否则转过程(2.22)；(2.13)在磁盘上分配块号为U的磁盘块为一个新哈希桶，将HT的第N项值置为U，将N置为N+1；(2.14)判断是否N＞2I，是则顺序进行，否则转过程(2.16)；(2.15)将I置为I+1；(2.16)判断N‑1的I位二进制形式第一位是否为1，是则顺序进行，否则转过程(2.23)；(2.17)将N‑1的I位二进制形式的低I‑1位换算成整数，记为K，将第二操作桶址D2置为HT中第K项的值，将块号为D2的磁盘块内容读到内存中的第二映射桶，第二记录号S初始化为0；将第一操作桶址D1置为HT中第N‑1项的值，将块号为D1的磁盘块内容读到内存中的第一映射桶，将Splitflag置为1；(2.18)在第二映射桶中取出第S个记录，判断该记录哈希值的二进制形式从右往左的第I位是否等于1，是则将第二映射桶中第S个记录置为空，将第二映射桶的内容写回到块号为D2的磁盘块中，转过程(2.4)，否则顺序进行；(2.19)第二记录号S+1后除以J，所得余数赋予记录号S，判断是否S＝0，是则顺序进行，否则转过程(2.18)；(2.20)判断第二映射桶是否有溢出桶，是则顺序进行，否则置Splitflag＝0，转过程(2.23)；(2.21)将D2置为第二映射桶的溢出桶地址，将溢出桶内容从磁盘读到内存中的第二映射桶，转过程(2.18)；(2.22)判断是否Splitflag＝0，是则顺序进行，否则转过程(2.19)；(2.23)将内存中的映射结构体内容写回到磁盘块W中，等待用户操作，分别转步骤(2)、(3)、(4)；(3)记录查找步骤：在读对象，写对象或者查看对象属性信息时进行，顺序进行下述过程：(3.1)从内存映射结构体中，取参数I、N、HT，以对象标志符为关键字，根据哈希函数，计算出哈希值，取出哈希值对应的二进制形式的低I位，并将该低I位二进制数换算为整数，记为M；(3.2)判断是否M＜N，是则顺序进行，否则转过程(3.9)；(3.3)将块号为HT中第M项值的磁盘块内容读到内存中的映射桶；(3.4)主记录号H置为哈希值除以J的余数，记录号A初始化为主记录号H；(3.5)在映射桶中取出第A个记录，判断该记录的关键字是否为要查找的对象标志符，是则顺序进行，否则转过程(3.7)；(3.6)返回第A个记录，转过程(3.12)；(3.7)记录号A+1后除以J，所得余数赋予记录号A，判断是否A＝H，是则顺序进行，否则转过程(3.5)；(3.8)判断映射桶是否有溢出桶，是则顺序进行，否则转过程(3.11)；(3.9)将溢出桶内容从磁盘读到内存中的映射桶，转过程(3.5)；(3.10)将M设置为M‑2(I‑1)，转过程(3.3)；(3.11)返回空记录；(3.12)等待用户操作，分别转步骤(2)、(3)、(4)；(4)记录删除步骤：在删除一个已存在的对象时，进行下述过程：(4.1)从内存映射结构体中，取参数I、N、R、HT，以对象标志符为关键字，根据哈希函数，计算出哈希值，取出哈希值对应的二进制形式的低I位，并将该低I位二进制数换算为整数，记为M；(4.2)判断是否M＜N，是则顺序进行，否则转过程(4.9)；(4.3)将操作桶址D置为HT中第M项的值，将块号为D的磁盘块内容读到内存中的映射桶；(4.4)主记录号H置为哈希值除以J的余数，记录号A初始化为主记录号H；(4.5)在映射桶中取出第A个记录，判断该记录的关键字是否为要查找的对象标志符，是则顺序进行，否则转过程(4.7)；(4.6)删除映射桶中第A个记录，将映射桶的内容写回到块号为D的磁盘块中，将R置为R‑1，将内存中的映射结构体内容写回到磁盘块W中，转过程(4.11)；(4.7)记录号A+1后除以J，所得余数赋予记录号A，判断是否A＝H，是则顺序进行，否则转过程(4.5)；(4.8)判断映射桶是否有溢出桶，是则顺序进行，否则转过程(4.11)；(4.9)将操作桶址D置为映射桶的溢出桶地址，将溢出桶内容从磁盘读到内存中的映射桶，转过程(4.5)；(4.10)将M设置为M‑2(I‑1)，转过程(4.3)；(4.11)等待用户操作，分别转步骤(2)、(3)、(4)；所述步骤(2)、(3)、(4)根据用户操作类型独立运行；所述记录由对象标志符和对象索引节点块号组成，其中对象标志符为128位的无符号整数，对象索引节点块号为相应对象索引节点在磁盘上的块号；所述索引结构体，是一个数据结构，由I、N、R、HT 4个参数组成，其中，I为二进制形式表示的哈希值中当前被使用的位数，N为当前哈希桶数，R为当前记录总数，HT为含有N个表项的哈希表，它的每个表项存放对应哈希桶在磁盘上的地址，以便通过它可以找到对应的哈希桶；所述映射结构体，是一个数据结构，位于内存中，其数据结构和索引结构体相同；所述哈希桶，是一个存储单元，由磁盘上固定数目的磁盘块构成，它最多存放J个记录和一个32位的溢出桶地址，所有记录的对象标志符的哈希值的右边I位均相同，I由索引结构体中指定；所述哈希表，为含有N个表项的表，它的每个表项存放对应哈希桶在磁盘上的地址，以便通过它可以找到对应的哈希桶。