Comments (3)
- 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
from concurrent-data-structure.
B-Tree가 AVL Tree나 RB Tree와는 다르게 단순히 removal에서 비워놓고 나중에 치우는 구조가 불가능하다. 왜냐하면 edge로부터 채워넣는게 크기가 안 맞으면 거의 불가능하기 때문... 위의 논문들에서도 인접한 sibling으로부터 값을 가져온다는 등의 전략을 취하는 거 같긴 하다.
from concurrent-data-structure.
일단은 다음과 같이 분석을 하였다.
- 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를 쓰기로 잠정적으로 결론 지음
from concurrent-data-structure.
Related Issues (10)
- Lock-based AVL tree에 관한 고민 HOT 3
- Concurrent ART에 관한 연구 HOT 3
- Benchmark 자동 작성을 위한 GitHub Bot 만들기 HOT 2
- RwLockAVLTree concurrent 테스트 deadlock 관찰 HOT 1
- Michael-Scott Queue 원본 논문의 오류 HOT 1
- 모든 Queue 구현체 메모리 누수 확인
- SeqLockAVLTree removal 병목
- Sequential Tree들과 SeqLockAVLTree 비교 HOT 2
- Concurrent HashMap에 대한 연구 HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from concurrent-data-structure.