java - In-Memory单表数据库算法或库

Question

从我要解决的问题开始:

• 给定一个类似平面表格的结构(行和列) 数据量较小(少于 50,000 行)
• 我需要在给定列索引数组的情况下快速找到匹配的行 使用精确相等匹配。 (通常会有 2-3 列 涉及给定的查询)
• 最多 1000 个针对所有必须在其中完成的数据的查询 1秒
• 数据可以批量添加或异步更新
  将再次开始查询
• 查询可以(理想情况下应该)并行运行
• 在运行查询时数据是不可变的
• 基于 Java

我查看了一些内存数据库，如 H2 和 VoltDB，但 SQL 开销在搜索中占主导地位，即使使用 PreparedStatements 也是如此。不可变 Object[][] 的全表扫描在一定程度上可以工作，但在表中留下了很多优化(比如索引)。如果我开始构建索引和边缘集，感觉就像我在重新发明数据库。

对于可以处理此问题的现有开源库或数据结构有什么建议吗？还是我最好继续我的“在这里发明”方法并开始滚动我自己的索引？对于我的“在这里发明”的方法，我使用 Object[][] 来处理数据并对其进行编码(使用 Akka 并行高达 1000 倍):

public int[] findMatchingRows(int[] columnIndex, Object[] columnValues){
   List<Integer> matchingRows = new ArrayList<Integer>();
   for(int row=0;i<data.length; row++){
     boolean found = true;
     for(int colIdx=0;j<columnIndex;colIdx++){
         if(!matches(data[row][columnIndex[colIdx], columnValues[colIdx]){
            found = false;
            break;
         }
     }
     if(found){
       matchingRows.add(row);
     }
   }
   return matchingRows;
}

Answer 1

一个简单的手动方法是，对于每个“索引”列，将所有行放入 HashMap<ColumnType, HashSet<Row>> 中，以便每个不同的键值映射到该列中具有该键值的所有行的列表。可以通过获取所有 HashSet<Row> 来执行查询对于查询中的键值，并取它们的交集。

预期的时间复杂度为 O(km)，其中 k 是查询中的键数，m 是来自任何键列的最大命中数。