在日志结构文件系统中查找记录的算法

Question

我有记录日志。每条记录都有一个 ID 和时间戳。新记录以单调递增的 ID 附加到日志中，即使中间的记录可以被删除。

问题是 - 如果给定时间戳 T1，请提供一种有效的算法来确定时间戳 = Ceil(T1) 的日志记录。

注意事项。日志可能非常大，有数百万条记录。由于记录删除，可能会丢失记录。

例子：如果日志记录=(ID, Timestamp)，那么日志可以这样显示：

(1, 10), (2, 11), (5, 15), (8,18), (9, 19), (10, 20)

查找最小时间戳大于或等于 17 的记录的 ID。

答案是 8。

查找最小时间戳大于或等于 11 的记录的 ID。

答案是 2。

查找最小时间戳大于或等于 22 的记录的 ID。

答案为无

查找最小时间戳大于或等于 5 的记录的 ID。

答案是 1

我想出了简单的数据结构来解决这个问题。

/* index:    0  1   2   3   4  5  6   7   8  9  10   11   12  */

int ids[]=     {1,  2,            6,  7,        10,  11,  12};
int map[]=  {0, 1,  1,  0,  0, 0, 1,  1,  0, 0, 1,   1,   1};
int time[]= {0, 10, 20, 0,  0, 0, 60, 70, 0, 0, 100, 110, 120};
int start= 1, end = 12;  // this is known to us.

ids[] 是所有 ID 的列表。鉴于此列表可能有数百万，我们无法在数组中索引此列表。因此在上面的示例中，ID 3、4、5、8、9 丢失了。但是这个列表是递增的。

map[] 是位图，可以告诉您给定的 ID 是否存在。这是一个便宜的操作。

time[] 是每个存在的 ID 的时间戳数组。请记住假设获取时间戳实际上是一项昂贵的操作。

ID 和时间戳值之间也没有相互关系。它可以是 1133、2987 等，而不是 10、20 等。但顺序递增。

你需要填写这个功能：

int
find_ceil_id(int timestamp) 
{
  .....
  ....
  return(id)
}

Answer 1

如果此函数在搜索之间保留在内存中，我们可以利用以前的搜索来缩小未来的搜索范围。如果获得时间戳的成本很高，那么这可能是一个非常显着的改进。但是，如果它们已经在您的 post 中的数组的内存中，那么这主要是一个有争议的问题。假设时间戳是唯一的，我会从这个开始作为解决方案：

int FindFirstNonZero(int startIdx)
{
    int myIdx=startIdx;
    while (map[myIdx] == 0)
    {
        myIdx++;
    }
    return(myIdx);
}

int FindLastNonZero(int startIdx)
{
    int myIdx=startIdx;
    while (map[myIdx] == 0)
    {
        myIdx--;
    }
    return(myIdx);
}

int find_ceil_id(int timestamp) 
{
    int low=FindFirstNonZero(0);
    int high=FindLastNonZero(map.count -1);
    int checkIndex = FindLastNonZero((low + high)/2);
    int checkTime;

    while (low < FindLastNonZero(high - 1))
    {
        checkTime = time[checkIndex];
        if (checkTime >= timestamp) {
            high = checkIndex;
        } else {
            low = checkIndex;
        }
        checkIndex = FindLastNonZero((low+high) / 2);
        if (checkIndex == low) {
            checkIndex = FindFirstNonZero(low+1);
        }
    }
    return (high);
}

从您的一些评论来看，时间戳似乎可以重复。是这样吗？如果是这样，就需要对上面的内容做一点小改动......没关系，进行更改甚至可以使代码更简单。

这是一个基本的二进制搜索，它将在 log2(N) 次尝试中找到正确的元素，N 是 ID 数组的大小。因此，对于 ID 数组中超过 100 万个条目，只需检查其中的 20 个条目即可找到正确的条目。对于超过 10 亿个条目，它只需要检查 30 个。

我不会编译和测试代码，这取决于您。但它应该有效。

在日志结构文件系统中查找记录的算法

Algorithm to find record in a log structured file system

algorithm

logging

data-structures

filesystems