在CSB +樹上的節點內搜索

Question

我正在閱讀論文making B+-trees cache conscious in main memory。在第3.1.2節中，作者描述了在CSB +樹節點內搜索的幾種方法。

Tha basic方法是簡單地使用常規while循環進行二分搜索。

的均勻方法是通過代碼擴充，展開而循環進入if-then-else語句假定所有的鍵被使用。

作者給出了下面的例子，展示了對一個節點的搜索展開，最多9個鍵。在一個節點的數字表示在if測試所使用的鍵的位置

   4 
      / \ 
      2  6 
     /\ /\ 
     1 3 5 8 
       /\ 
       7 9 

然後是混淆的部分：

如果只有5個鍵是實際存在，我們可以遍歷這個樹正好與比較。另一方面，將最深的子樹置於左側而不是右側的展開將需要某些分支上的比較。

那麼，爲什麼它需要更多的比較在下面的樹：

   6 
      / \ 
      4  8 
     /\ /\ 
     2 5 7 9 
     /\ 
     1 3 

此外，

如果我們知道我們只有五個有效按鍵，我們可以硬編碼樹，平均而言，使用2.67比較而不是3.

2.67是怎麼產生的？

任何提示將不勝感激。此外，一個鏈接指向我代碼擴展知識將是有益的。

實際上，我不確定在紙上提出問題是否合適，因爲在此處轉錄時可能遺漏了一些關鍵信息（問題可能需要重新格式化）。我只希望能有人碰巧看過這篇論文。

由於

Answer 1

這裏的關鍵點是從相同的部分以下引號：

我們墊所有 未使用的密鑰（密鑰列表[nKeys..2d-1]）中的一個節點 與最大可能的鍵

也是很重要的是，在B +/CSB +樹我們不搜索節點值，但是這些值之間的間隔。一組可能的值由5個鍵分成6個區間。

由於大多數右子樹充滿了最大可能的密鑰（L），我們需要比平常少的比較：

   4 
      / \ 
      2  L 
     /\ /\ 
     1 3 5 L 
       /\ 
       L L 

根節點的右後代已經最大可能的密鑰，沒有需要檢查任何節點的權利。並且需要爲每間隔正好3的比較：

interval comparisons 
up to 1 k>4, k>2, k>1 
1..2  k>4, k>2, k>1 
2..3  k>4, k>2, k>3 
3..4  k>4, k>2, k>3 
4..5  k>4, k>L, k>5 
5..L  k>4, k>L, k>5 

如果我們把最深的子樹在左邊，我們有一棵樹，其中非空節點放置更深一層：

   L 
      / \ 
      4  L 
     /\ /\ 
     2 5 L L 
     /\ 
     1 3 

搜索此樹節點「1」要求比較4個不同節點的關鍵：L，4,2和1

如果我們知道，我們只有五個有效的密鑰，我們有以下樹：

   2 
      / \ 
      1  4 
       /\ 
       3 5 

在這裏，我們可以安排的方式比較，給出了平均2.67的比較：

interval comparisons 
up to 1 k>2, k>1 
1..2  k>2, k>1 
2..3  k>2, k>4, k>3 
3..4  k>2, k>4, k>3 
4..5  k>2, k>4, k>5 
5..L  k>2, k>4, k>5 

「代碼膨脹」並不是一個廣泛使用的術語，所以我不能給你最相關的鏈接。我認爲，這與"Loop unwinding"差別不大。