经由位图的树表示分配文件存储的方法和设备

摘要

本发明涉及经由位图的树表示分配文件存储的方法和设备。描述了搜索位图的树表示来找到存储装置中待分配的可用区块的方法和设备。可以接收针对文件的分配请求，以开始搜索。在一个实施例中，位图可包括与存储装置中的区块对应的位的阵列。每个位可指示区块之一是否可用的。树表示可包括具有节点的至少一个红黑树，所述节点对应于位图中指示可用区块范围的一个或多个连续位。可以根据与分配请求相关联的文件来选择一个树表示，以识别与所述分配请求匹配的可用区块范围。当位图随着存储装置中的区块分配的改变而被更新时，树表示可以被同步。

主权项

一种用于实现文件系统的计算机实现方法，所述方法包括：响应于在至少一个存储装置中为文件分配空间的请求，从位图的多个树表示中选择一个树表示，其中所述位图中的每个位指示所述至少一个存储装置中的区块的可用性；搜索所选择的树表示的一个或多个节点以找到第一节点，所述第一节点的相应的一个或多个连续位具有与由所述请求指定的区块的数量相匹配的大小；判定所述第一节点不包含在所选择的树表示的所述一个或多个节点中；响应于所述判定，搜索所选择的树表示的所述一个或多个节点以找到第二节点，所述第二节点的相应的一个或多个连续位具有不同于由所述请求指定的区块的数量的大小，其中该不同在预定的阈值之内；更新所述位图，以分配与所述第二节点相对应的区块；以及将所述多个树表示中的每个树表示与更新后的位图同步。