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页面。