Java中排序后的（内存映射？）文件中的二进制搜索

Question

我正在努力将Perl程序移植到Java，并在学习过程中学习Java。原始程序的核心组件是Perl模块，该模块使用二进制搜索在+500
GB排序的文本文件中执行字符串前缀查找（本质上是“寻找”到文件中间的字节偏移，回溯到最近的换行符，然后进行比较）带有搜索字符串的行前缀，“搜索”为字节偏移量的一半/两倍，重复直到找到…）

我已经尝试了几种数据库解决方案，但是发现使用这种大小的数据集，在纯粹的查找速度上没有比这更好的了。您是否知道任何实现这种功能的Java库？失败了，您能否指出一些惯用的示例代码，该示例代码会随机访问读取文本文件？

另外，我不熟悉新的Java Java I / O库，但是是否可以选择将内存映射到500
GB的文本文件（我在64位计算机上，有空闲的内存）并执行二进制操作在内存映射的字节数组上搜索？我很想听听您必须分享有关此问题和类似问题的任何经验。

Answer 1

我是一个 很大的 Java的风扇
MappedByteBuffers
像这样的情况。它正在迅速燃烧。下面是我为您整理的一个片段，该片段将缓冲区映射到文件，查找到中间，然后向后搜索换行符。这应该足以让您继续前进吗？

我有类似的代码（寻找，读，重复，直到完成）在我自己的应用程序，基准
java.io针对流MappedByteBuffer在生产环境和贴在我的博客的结果（Geekomatic文章标签“的java.nio”）与原始数据，图表和所有。

两秒钟的总结？ 基于 我MappedByteBuffer的实现速度提高了约275％。 YMMV。

为了处理大于〜2GB的文件，这是一个问题，因为强制转换和.position(int pos)，我精心设计了由MappedByteBuffers
数组支持的分页算法。您需要使用64位系统才能处理大于2-4GB的文件，因为MBB使用操作系统的虚拟内存系统来发挥其魔力。

public class StusMagicLargeFileReader  {
    private static final long PAGE_SIZE = Integer.MAX_VALUE;
    private List<MappedByteBuffer> buffers = new ArrayList<MappedByteBuffer>();
    private final byte raw[] = new byte[1];

    public static void main(String[] args) throws IOException {
        File file = new File("/Users/stu/test.txt");
        FileChannel fc = (new FileInputStream(file)).getChannel(); 
        StusMagicLargeFileReader buffer = new StusMagicLargeFileReader(fc);
        long position = file.length() / 2;
        String candidate = buffer.getString(position--);
        while (position >=0 && !candidate.equals('\n')) 
            candidate = buffer.getString(position--);
        //have newline position or start of file...do other stuff    
    }
    StusMagicLargeFileReader(FileChannel channel) throws IOException {
        long start = 0, length = 0;
        for (long index = 0; start + length < channel.size(); index++) {
            if ((channel.size() / PAGE_SIZE) == index)
                length = (channel.size() - index *  PAGE_SIZE) ;
            else
                length = PAGE_SIZE;
            start = index * PAGE_SIZE;
            buffers.add(index, channel.map(READ_ONLY, start, length));
        }    
    }
    public String getString(long bytePosition) {
        int page  = (int) (bytePosition / PAGE_SIZE);
        int index = (int) (bytePosition % PAGE_SIZE);
        raw[0] = buffers.get(page).get(index);
        return new String(raw);
    }
}