c - 如何实现这篇 T-link-tree 论文中搜索功能使用的“闩锁”功能？

Question

在这篇论文中，Tlink-tree: Main memory index structure with concurrency control and recovery by Jan Lindström，我们展示了以下算法：

Search(key, P) {
  P = root page; 
  slatch(P);
  do {
    h = high-key(P);
    l = low-key(P);
    if (key < l) {
      Q = P.left;
      slatch(Q);
      unlatch(P);
      P = Q;
    } else if (key > h) {
      if (P is a leaf page) {
        Q = P.successor;
      } else {
        Q = P.right;
      }
      slatch(Q);
      unlatch(P);
      P = Q;
    } else {
      search key from P;
      if (bounding key value found) {
        slatch(P.ptr); 
        R = P.ptr; 
        unlatch(P);
        search key from R;
      }
      return R or NULL if not found;
    }
  } while (P);
}

此外，我们还有以下注意事项：

• slatch(P): 修复页面 P 并获取 P 上的共享锁存器。
• xlatch(P): 固定页面 P 并获取 P 上的独占锁存器。
• unlatch(P)：松开 P 页上的闩锁并取消固定 P。
• slock(r)：获取记录 r 上的无条件共享锁。
• xlock(r)：获取记录 r 上的无条件排他锁。
• unlock(r): 释放记录 r 上的锁。

我想知道如何在 JavaScript 中表示它，以便更好地理解它在实践中是如何工作的。还没有，需要弄清楚这个search函数的数据结构（JSON 表示）和其他细节：

function search(tree, key) {
  let node = tree
  slatch(node)
  do {
    let h = node.highKey
    let l = node.lowKey
    if (key < l) {
      let newNode = node.left
      slatch(newNode)
      unlatch(node)
      node = newNode
    } else if (key > h) {
      let newNode
      if (node is a leaf page) {
        newNode = node.successor
      } else {
        newNode = node.right
      }
      slatch(newNode)
      unlatch(node)
      node = newNode
    } else {
      search key from node
      if (bounding key value found) {
        slatch(node.ptr) 
        R = node.ptr 
        unlatch(node)
        search key from R
      }
      return R or NULL if not found
    }
  } while (node)
}

我在这篇文章中的问题是，我不明白slatch和相关的函数（和P）在做什么，或者如果你用 C （在深层次的技术层面）实现它，它们会做什么。他们的意思是什么？例如，他们会在 C 中准确地做什么？或者，如果您要使用 webworkers 在 JavaScript 中实现此功能，您是否也需要此功能？那时会是什么样子？这种方法的实现是什么？

他们在论文中指出：

锁存器由提供廉价同步机制但不检测死锁的低级原语（信号量）实现。可以使用有条件或无条件选项进行锁定请求。条件请求意味着如果不能立即授予锁，请求者（事务）不愿意等待。无条件请求意味着请求者愿意等待直到授予锁。我们使用生理测井 [18] 作为物理测井和逻辑测井之间的折衷。我们假设缓冲区管理器采用窃取和无强制缓冲策略 [18]。

我正在阅读这篇文章以了解更多关于 t-trees 的背景信息。

标签： calgorithmconcurrencytreelocking