## A C++11 implementation of the B-Tree part of "The Case for Learned Index Structures"
A research **proof of concept** that implements the B-Tree section of [The Case for Learned Index Structures](https://arxiv.org/pdf/1712.01208.pdf) paper in C++.
The general design is to have a single lookup structure that you can parameterize with a KeyType and a ValueType, and an overflow list that keeps new inserts until you retrain. There is a value in the constructor of the RMI that triggers a retrain when the overflow array reaches a certain size.
The basic API:
```c++
// [first/second]StageParams are network parameters
int maxAllowedError = 256;
int maxBufferBeforeRetrain = 10001;
auto modelIndex = RecursiveModelIndex recursiveModelIndex(firstStageParams,
secondStageParams,
maxAllowedError,
maxBufferBeforeRetrain);
for (int ii = 0; ii < 10000; ++ii) {
modelIndex.insert(ii, ii * 2);
}
// Since we still have one more insert before retraining, retrain before searching...
modelIndex.train();
auto result = modelIndex.find(5);
if (result) {
std::cout << "Yay! We got: " << result.get().first << ", " << result.get().second << std::endl;
} else {
std::cout << "Value not found." << std::endl; // This shouldn't happen in the above usage...
}
```
See [src/main.cpp](src/main.cpp) for a usage example where it stores scaled log normal data.
### Dependencies
- [nn_cpp](https://github.com/bcaine/nn_cpp) - Eigen based minimalistic C++ Neural Network library
- [cpp-btree](https://code.google.com/archive/p/cpp-btree/) - A fast C++ implementation of a B+ Tree
### TODO:
- Lots of code cleanup
- Profiling of where the slowdowns are. On small tests, the cpp_btree lib beats it by 10-100x
- Eigen::TensorFixed in nn_cpp would definitel
2021-09-03 13:57:46
402KB
1
该程序使用kd-B Tree（结合了kd-trees和B-trees的特性）来存储商家。 因为商家列表理论上是无限的，更简单的 kd-tree 是不可接受的，因为它不允许动态插入。 我还修改了 kd-B 树，以允许我们在查询时按类别进行过滤。 如果有太多条目无法放入内存，则可以轻松地将树更改为使用辅助存储。
我选择了 Ruby，以便可以轻松地将树包含到 RoR 或 Sinatra 项目中。 我还包括 rspec 测试以确保树正常运行。
参考
Robinson, John T.“KDB 树：大型多维动态索引的搜索结构”，卡内基梅隆大学，匹兹堡，1981 年。
2021-07-12 14:04:45
228KB
1