故事是这样的。年初的时候审查一个快速键值对查询功能的代码，原本的设计是把Java的Map结构简单的持久化并在查询时候进行反序列化，由于大数据的IO操作会比较慢，我便自告奋勇设计一个新的键值对查询模块。随后我查阅了很多资料，对一篇2011年底发表的关于基于SSD和内存索引的论文十分感兴趣，其超低的内存占用和常数访问效率正好满足功能的要求。于是我便利用放假的一个礼拜做了一个Java的实现，初步实验数据和论文表述的完全一致，只剩下把原来的模块切换过来。但由于项目重点发生变化，我被迫转到了另一个功能开发上，这个切换的工作也就搁置下来。就在项目进入最后性能调优的阶段，这个切换工作被提到了日程上。可是切换工作非常不顺利，先是遇到OOM，随后发现虽然查询性能很优秀，索引构建的过程则异常缓慢，还出现了长时间没响应的情况。原来虽然这个方法的内存占用很少，只有3比特每个键值对，但从算法复杂度来说，还是O(n)的，也就是说，只要键值对足够多，内存就会被消耗完毕。这种表现对于嵌入式的键值对查询模块来说，是致命的，因为目前系统的设计并没有采用分区或者分片的方法，也就是说用户输入的规模是不可控制的。索引构建的过程也是异常辛苦，原本这个方法的初衷是想实现在写入的同时保持高效查询，所以采用了三阶段的数据结构。可事实上，实际系统只要求一次创建过程，完成后就是只读的状态，无疑三阶段数据结构的转换本身消耗了大量无谓的时间。

这其中的教训就是：

当然问题还没有完全解决，现在我需要找O(1)内存占用，以及O(logn)查询效率的方案了。