B C＃和JavaScript中的樹和稀疏索引算法

Question

TLDR;

您可以在使用JavaScript或C＃寫入磁盤時定位磁盤塊。當你有固態硬盤時，它有什麼關係嗎？

問題

我在JavaScript和C＃中創建了BTree實現。

在閱讀this section of wikipedia on btrees它討論稀疏索引和降低磁盤讀取。

在我看來，它正在討論將索引和記錄分組到磁盤塊以加速讀取它們。

問題

我有幾個問題：

1. 罐體C＃或JavaScript（節點）目標磁盤塊，或者是你有東西在你的代碼計算？即使用HDD的分區表求出相應的塊大小和塊數據？

2. 當我們擁有SSD時，磁盤塊讀取是否重要？

跟進

顯然在C＃中，您可以創建FileStream S和BinaryWriter秒或StreamWriter S中，但只需要byte[]，你不能在特定的任何位置指定磁盤上 - 而且說實話，我預計大部分寫入磁盤的操作都是在較低級別上進行的 - 比如內核和磁盤驅動程序......

使用固態硬盤讀取使得所有的東西都可以快得多，如此有效，只要BTree節點保持參考到確切的文件和字節標記（或類似的東西），然後指定i在C＃中很容易 - 無論如何快速閃電。這將是一個簡單的reader.Seek(/** some offset **/)，然後在記錄中讀取。

我甚至不知道從哪裏開始與節點來試試這個，它只是有其簡單的fs.writeFile()功能....

Answer 1

1）高級語言如C＃和JavaScript通常不來特定於塊操作的API，但不必查詢分區表或任何內容來確定塊大小。

扇區通常保存512字節的數據，但是對於您的應用程序而言，最佳大小可能大於一個扇區。從磁盤讀取昂貴的部分是（基本上）將磁盤磁頭移動到所需的磁道上，然後等待要在磁盤上旋轉的扇區來滿足它。

想想旋轉磁盤上扇區的軌跡。在磁頭移動到它想要讀取的扇區後，磁盤上的下一個扇區就已經在那裏了。如果你想立即閱讀這個領域，那麼你根本不需要做任何昂貴的移動。

由於這個原因，讀取幾個連續的扇區只比讀取一個扇區貴一點點，通常你可以使用額外的數據來獲得某些東西。

當您的操作系統需要緩存磁盤上的內存或數據時，它將以4K塊的形式讀寫。你應該認爲這是最低限度。

在爲您的B-tree選擇塊大小時，請計算出每塊中您將擁有多少個密鑰，並通過將額外閱讀成本（相對便宜）與成本進行折扣來選擇大小不得不穿越額外的水平，因爲你的塊太小（相對昂貴）。你應該測試，但是你的理想模塊很可能會比4K更大。

2）使用固態硬盤時，權衡是不同的。您不再需要擔心移動磁頭和旋轉磁盤的成本，但讀取連續扇區仍然更快。你應該再次測試。你會發現最佳的扇區尺寸更小。儘管如此，由於數據通過操作系統內存緩存，因此您仍然不應該小於4K，並且無論如何通常都會使用4K頁面。