C＃通用B +樹

Question

我正在使用C＃實現B +樹。現在據我所知，一個樹節點應該保存一些（order-1）鍵，並且指向記錄或其他節點的指針數量，也就是說，只有葉節點會保存實際指向記錄的指針，並且內部節點將保存指向其他節點的指針。

我正在與該實現遇到的問題是與C＃泛型

節點類被聲明爲：

class Node< K,V > 
{ 
    K [] keys ; 
    V [] values; 
} 

現在，當我嘗試將節點放入值數組作爲這樣

_root.Values[0] = left ; // left being of type Node<K,V> 

我收到以下錯誤：

Cannot implicitly convert type 'BTree_Library.Node' to 'V'

所以，我試圖找到一種方法來解決這個問題，另一種選擇是更改實現來保存一個節點的數組和一個記錄。

所以，結論是：

1. 在C我會用：(void* values;) 我正在尋找的，在C＃中的等價。

2. 雖然我們在這個問題上，我是否正確理解B +樹結構 參考節點和記錄是否可以互換節點指針？

Answer 1

您希望您的葉節點和內部節點的行爲不同，同時仍可以將它們都稱爲節點。這說明一個繼承層次：

abstract class Node<K, V> 
{ 
    public K[] Keys { get; protected set; } 
} 

class LeafNode<K, V> : Node<K, V> 
{ 
    public V[] Values { get; protected set; } 
} 

class InnerNode<K, V> : Node<K, V> 
{ 
    public Node<K, V> Children { get; protected set; } 
} 

另一種選擇是使用C＃相當於void*，這是object，但是這意味着代碼不是類型安全了，你就必須有強制轉換無處不在。我不會推薦這樣做。

這就是說，你爲什麼要創建自己的B-樹？只有在將數據保存在磁盤上而不是內存中時纔有用。如果你只是做了關聯數組，那麼.Net中的類已經實現了它（如Dictionary<K,V>或SortedDictionary<K,V>），並且工作得很好。

Answer 2

假設_root.Values[0] = left被從類中執行的，並且Values相當於values的性質。

，如果V將永遠是一個類型的Node，你可以嘗試像

interface INode { 
} 

class Node<K, V> : INode where V : INode { 

} 

這將迫使V2從BTree_Library.Node推導，這將使該行沒有任何錯誤編譯。

如果V不會總是從Node派生，那麼我認爲泛型可能是解決這個問題的錯誤方法。