Concurrent BTree 구현에 대한 연구

[codingskynet]

논문을 모아두거나, 이것저것 정리해서 아이디어를 정리해놓는 이슈

[codingskynet]

• https://core.ac.uk/download/pdf/144148591.pdf
• https://www.researchgate.net/profile/Faith-Ellen/publication/221344000_Non-blocking_Binary_Search_Trees/links/09e4150a26e6f2d9de000000/Non-blocking-Binary-Search-Trees.pdf
• https://arxiv.org/pdf/1712.05020.pdf
• https://imada.sdu.dk/~kslarsen/Papers/Resources/LF96j/paper.pdf
• https://wiki.eecs.yorku.ca/course_archive/2010-11/W/6490A/_media/public:elise.pdf

[codingskynet]

B-Tree가 AVL Tree나 RB Tree와는 다르게 단순히 removal에서 비워놓고 나중에 치우는 구조가 불가능하다. 왜냐하면 edge로부터 채워넣는게 크기가 안 맞으면 거의 불가능하기 때문... 위의 논문들에서도 인접한 sibling으로부터 값을 가져온다는 등의 전략을 취하는 거 같긴 하다.

[codingskynet]

일단은 다음과 같이 분석을 하였다.

• B-tree를 쓰기는 좋지 않다. 왜냐면 removal시 successor나 predecessor와 replace하고 제거하는 것이 일반적인 invariant인데, concurreny 환경에서는 이게 상당한 bottleneck이 되기 때문이다.
• 설령 위의 문제를 해결한다고 relaxed를 한다고 하더라도, 메모리 낭비가 심하고 복잡도가 상당히 높아질 것으로 예상된다. 가뜩이나 B-tree는 최악의 경우 tree의 50% 공간을 낭비하는데도 말이다. AVL때처럼 대충 비워놓고 나중에 처리하는 것은 상당히 비효율적일 듯.

따라서 internal node에 key를 가지지 않은 B+-tree쪽이 concurrent하게 만들기 좋아보이는데, 일단 역시 얘도 귀찮을 거 같고, ART 논문에서 ART가 더 우수하다고(일단은) 벤치마크를 제시했으며, 차후에 key-value in-memory DB를 만들 때에 key는 항상 String을 가져갈 것으로 예상되기 때문에 굳이 Trie를 안 쓸 이유는 없어 보이므로, Trie의 일종인 ART를 쓰기로 잠정적으로 결론 지음