## 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
1