块存储

Question

我想将几个条目存储到一个文件中(为读取优化)，并为其提供一个好的数据结构，这似乎是一个B+树。它提供了一个O(log(n)/log(b))访问时间，其中b是一个块中的条目数。

描述B+树的文献很多，但总的来说，基于块的存储系统还存在一些问题。也许有人能给我指明正确的方向或者回答以下几个问题：

1. Do (所有常见的)文件系统在新块的开头创建新文件？那么，我是否可以确定into (0)会将读/写头设置为设备块大小的乘积？
2. 是否正确，我应该只使用pread(fd, buf, n * BLOCK_SIZE, p * BLOCK_SIZE) ( n，p是整数)之类的调用来确保始终读取完整的块？
3. 是否更好地将() BLOCK_SIZE字节读入数组或mmap()？或者，如果我映射了多个块而只访问了几个块，就会有区别吗？还有什么更好呢？
4. 应该通过在每个块的末尾添加填充字节来避免产生多个块的键？我也应该通过在数据之间添加填充字节来对叶节点进行同样的操作吗？

非常感谢，

克里斯多夫

Answer 1

通常，

1. 文件系统在新块的开头创建新文件，因为底层设备就是这样工作的。硬盘是块设备，因此不能处理小于“块”或“扇区”的任何东西。此外，操作系统根据页面来处理内存和内存映射，这些页面通常更大(扇区通常是512或1024字节，页面通常是4096字节)。

想到这个规则的一个例外是ReiserFS，它将小文件直接放入文件系统结构(如果我记得的话，它就是一棵B+树！)对于非常小的文件来说，这实际上是一种可行的优化，因为数据已经在内存中而没有另一次查找，但也可以是反优化，这取决于具体情况。

• 并不重要，因为操作系统无论如何都会将整页(通常为4kB)的数据读取到页面缓存中。读取一个字节将传输4kB并返回一个字节，读取另一个字节将从页面缓存中为您服务(如果相同的页面或位于readahead中的字节是通过从页面缓存复制数据来实现的，而mmap只是将页面映射到您的地址空间中(可能会根据您的保护标志在写上标记它们)。因此，mmap总是至少一样快，而且通常更快。mmap也比较舒服，但它的缺点是，当它需要获取更多内存中没有的页面时，它可能会被阻塞(但是，对于任何没有被锁定在内存中的应用程序或数据，这通常都是正确的)。另一方面，read会在你告诉它的时候阻止它，而不是其他。

在Windows环境下，情况也是如此，只有在Windows下的内存映射文件在高并发性下不能很好地扩展，因为缓存管理器序列化everything.

• Generally one试图保持数据紧凑，因为较少的数据意味着更少的页面，而更少的页面意味着它们在页面缓存中并适合于readahead范围的可能性更高。因此，我不会添加填充，除非出于其他原因，(alignment).

是必要的。

Answer 2

支持延迟分配的

1. 文件系统不会在磁盘上任何地方创建新文件。许多较新的文件系统支持将非常小的文件打包到自己的页面中或与元数据共享(例如，reiser将非常小的文件放入inode?)但对于较大的文件，大部分是这样的。
2. 可以做到这一点，但是OS页面缓存总是会读取整个块，只需将请求的位复制到应用程序的内存中。
3. 取决于您使用的是直接IO还是非直接IO。

如果您使用的是直接IO (它绕过操作系统的缓存)，则不使用mmap。大多数数据库不使用mmap，也不使用直接IO。

直接IO意味着页面不会通过OS的页面缓存，它们根本不会被OS缓存，也不会将其他块从OS缓存中推出来。这也意味着所有的读写都需要在块边界上完成。块边界有时可以通过文件系统上的statfs调用来确定。

大多数数据库似乎都认为它们应该自己管理自己的页面缓存，并且只使用操作系统进行物理读/写。因此，它们通常使用直接和同步的IO。

著名的莱纳斯·托瓦尔兹( Linus )不同意这种做法。我认为供应商这样做确实是为了在不同的OSs之间实现更好的行为一致性。

Answer 3

1. 是的。如果不这样做，会给FS设计带来不必要的麻烦。
2. 和选项(作为“仅”的替代)是.
3. 在Windows内存映射文件中的工作速度快于文件API (ReadFile)。我想在Linux上是一样的，但是您可以自己进行度量--