Bw-tree - это такая штука: придумано в microsoft в 2013. https://www.microsoft.com/en-us/research/publication/the-bw-tree-a-b-tree-for...
Вопрос про деление ноды. Есть нода P, которая делится. При делении P, мы создаём новую ноду Q, туда сливаем из ноды P все ключики >= kkk (делящий ключ). Нода Q сформирована и наступает момент времени (1). Далее лезем в ноду P добавлять delta-redirect-kkk-to-Q. Это происходит в момент времени (2). Между моментами (1) и (2) другой поток успел насрать в ноду P ключей >= kkk. После (2) возникает ситуация, что для >= kkk все ходят в Q, а части ключей >= kkk там нет. Как быть? При поиске проверять обе? Ещё вариант: при установке delta-redirect-kkk-to-Q в ноду P ставить эту дельту через CAS не просто относительно текущего состояния P, а относительно того состояния P которое было на момент начала копирования данных в Q. Тогда если между (1) и (2) кто-от поменяет P, дельта не вставится и мы снова запустим формирование Q заново. Но тут риск: если активно льются INSERT-ы в P, то состояние P будет постоянно новое и цикл попыток формирования Q будет делать дофига итераций. Накопал пару проектов китаеамериканских студентов с попытками это имплементить bw-tree, почитаю исходники ещё подробнее, хотя у них бывают заглушки с припиской TODO.