用于可变长度记录存储和仅在主键上搜索的磁盘上查找的数据结构/算法 [英] Data structure/algorithm for variable length record storage and lookup on disk withsearch only on primary keys

问题描述

我正在寻找一种算法/数据结构，该算法/数据结构适用于基于大型块的设备（例如机械硬盘），并且针对插入，获取，更新和删除进行了优化，其中始终使用数据ID进行搜索。

I am looking for an algorithm / data structure that works well for large block based devices (eg a mechanical hard drive) which is optimised for insert, get, update and delete where searches are always done using the id of the data and where the data fields for any ID have a variable length.

B树似乎是常用的结构，但主要用于固定长度的记录。与插入和删除相比，我还期望获得和更新的数量会大大增加。我可以摆脱对B树的O（log m）查找吗？

The B-Tree seems to be a commonly quoted structure but mainly for fixed length records. I also expect dramatically more gets and updates than I do inserts and deletes. Can I get rid of the O(log m) lookup of the B-tree?

我很高兴它成为一个组合系统，例如ISAM组合了一个可以使B树和线性文件存储看起来可以与可变长度记录一起使用。有什么更好的东西吗？

I am quite happy for it to be a combined system, for instance ISAM combines a B-tree and linear file storage which looks like it can be made to work with variable length records as an approach. Is there something better?

一些其他约束：

1）ID可能很稀疏，但可以将它们做成以线性数的块形式出现-但范围很大（64位）

1) IDs are potentially sparse but they can be made to come in blocks of linear numbers - but in a large range (64 bit)

2）我不想使用DBMS，对于我的特定问题，性能还没有证明不是很好。我不需要完整的DBMS使用的任何操作，也不需要搜索。我需要可以轻松调整和优化的内容。称其为学术上的好奇心，如果它是由MySQL执行的，那么我会用它，但我必须尝试并加快步伐。

2) I don't want to use a DBMS, performance for my particular problem hasn't proved very good. I don't need any of the operations a full DBMS uses, I don't need search. I need something I can tweak and optimise easily. Call it academic curiosity, if it is out performed by MySQL then I'll use that but I have to try and go faster.

3）数据集大于可以可以存储在内存中，但是如果索引与键，偏移一样简单，则索引很可能适合内存。我当然正在寻找大约10亿个实体或更多的存储空间。

3) The dataset is larger than can fit in memory, the index however may well fit into memory if its as simple as key, offset. I am certainly looking at something like 1 billion entities or more in storage.

4）理想情况下，删除记录时应该恢复空间。可能是通过压缩，但是我很想看看是否有更好的方法（例如，B树很容易恢复空间）。

4) Ideally space should be recovered when a record is deleted. That may be via compaction but I am interested to see if there is a better way (A B-tree for instance recovers space easily).

推荐答案

简单的方法：使用Berkeley DB之类的东西。它为任意字节字符串提供键值存储，并为您完成所有艰苦的工作。

The easy way: Use something like Berkeley DB. It provides a key-value store for arbitrary byte strings, and does all the hard work for you. It even provides 'secondary databases' for indexing, if you want it.

自己动手的方式：使用协议缓冲区（或您选择的二进制格式），甚至可以为索引提供辅助数据库。定义B树节点和数据项结构。对数据库使用仅附加文件。要写入新记录或修改现有记录，您只需将记录本身写入文件末尾，然后写入任何已修改的B-Tree节点（例如，记录的父节点， its 父节点） ，依此类推直至根源）。然后，将树的新根的位置写入文件开头的标头块中。要读取文件，您只需找到最新的根节点并像读取其他任何文件一样读取B树。这种方法具有几个优点：

The do-it-yourself way: Use Protocol Buffers (or the binary format of your choice) to define B-Tree node and data item structures. Use an append-only file for your database. To write a new record or modify an existing record, you simply write the record itself to the end of the file, then write any modified B-Tree nodes (eg, the record's parent node, its parent node, and so forth up to the root). Then, write the location of the new root of the tree to the header block at the beginning of the file. To read the file, you simply find the most recent root node and read the B-Tree like you would in any other file. This approach has several advantages:

• 由于从未修改过写入的数据，因此读者无需锁住并获得快照在开始读取时基于根节点查看数据库的视图。


• 通过在节点和记录中添加先前版本字段，您可以访问数据库的先前版本。基本上是免费的DB。


• 与大多数支持修改的磁盘文件格式相比，它确实易于实现和调试。


• 压缩数据库简单地读取数据和B-Tree的最新版本并将其写入新文件中。

• Since written data is never modified, readers don't need to take locks, and get a 'snapshot' view of the DB based on the root node at the time they started reading.
• By adding 'previous version' fields to your nodes and records, you get the ability to access previous versions of the DB essentially for free.
• It's really easy to implement and debug compared to most on-disk file formats that support modification.
• Compacting the database consists of simply reading out the latest version of the data and B-Tree and writing it to a new file.

这篇关于用于可变长度记录存储和仅在主键上搜索的磁盘上查找的数据结构/算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！