javascript - C# 和 JavaScript 中的 B 树和稀疏索引算法

Question

TLDR;

在用 JavaScript 或 C# 写入磁盘时，您能否定位磁盘 block 。当您拥有 SSD 时，这重要吗。

问题

我正在用 JavaScript 和 C# 创建一个 BTree 实现。

阅读中this section of wikipedia on btrees它讨论了稀疏索引和降低磁盘读取。

在我看来，它正在谈论将索引和记录分组到磁盘 block 中以加快读取它们的速度。

问题

我有几个问题:

1. C# 或 JavaScript (Node) 能否以磁盘 block 为目标，或者这是您必须在代码中计算的内容？ IE。是否可以利用硬盘的分区表计算出相应的 block 大小和 block 数据？

2. 当我们拥有 SSD 时，磁盘 block 读取是否如此重要。

跟进

显然，在 C# 中，您可以创建 FileStream 和 BinaryWriter 或 StreamWriter，但它们只需要 byte[]，你不能在磁盘上特别指定任何地方——老实说，我希望写入磁盘的大部分操作都是在较低级别处理的——比如内核和磁盘驱动程序……

使用 SSD 读取让一切变得更快、更有效，只要 BTree 节点保持对确切文件和字节标记(或类似的东西)的引用，然后在 C# 中指定它就很容易 - 而且无论如何都很快。这将是一个简单的 reader.Seek(/** some offset **/) 然后只读入记录。

我什至不知道从哪里开始尝试使用 Node，它只有简单的 fs.writeFile() 函数....

Answer 1

1) C# 和 JavaScript 等高级语言通常不附带专门对 block 进行操作的 API，但您不必查询分区表或任何东西来确定合适的 block 大小。

扇区通常包含 512 字节的数据，但您的应用程序的最佳大小可能大于一个扇区。从磁盘读取的昂贵部分是(基本上)将磁头移动到您想要的磁道，然后等待您想要在盘片上旋转的扇区满足它。

想想旋转磁盘上的扇区轨道。在磁头移动到它想要的扇区并读取它之后，磁盘上的下一个扇区已经就在那里。如果您想立即读取该扇区，则根本不需要进行任何昂贵的移动。

因此，读取几个连续扇区的开销只比读取一个扇区高一点点，而且通常您可以将这些额外数据用于某些事情。

当您的操作系统需要在磁盘上缓存内存或数据时，它会以 4K block 为单位进行读写。您应该将其视为最低限度。

在为 B 树选择 block 大小时，计算出每个 block 中要有多少个 key ，然后通过权衡额外读取的成本(相对便宜)与拥有的成本来选择大小遍历额外的级别，因为您的 block 太小(相对昂贵)。您应该进行测试，但您理想的 block 很可能会大于 4K。

2) 对于 SSD，权衡是不同的。您不再需要担心移动磁头和旋转盘片的成本，但读取顺序扇区仍然更快。你应该再测试一次。您会发现最佳扇区大小更小。不过，您仍然不应小于 4K，因为您的数据会通过操作系统内存缓存，而且通常无论如何都会使用 4K 页面。