서울대학교 데이터사이언스대학원 정형수 교수님의 "빅데이터 및 지식 관리 시스템 2" 강의를 필기한 내용입니다.
T-Tree
- T-Tree 는 AVL Tree (Database Index) 의 변형으로, 아래와 같은 알파벳 T 자 모양의 node 를 이용한다는 점에서 이런 이름이 붙었다.
- 보면 위로 Parent Pointer 가 있다. 즉, 이놈은 tree traversal 을 할 때 bidirection 으로 움직일 수 있는 것.
- 그리고 아래로는 Child Pointer 가 두개 있어서 child node 로 움직일 수 있게 해주고,
- 양옆으로는 Node Boundary 가 있다.
- 즉, Min Node Boundary 보다 작은 key 에 대해서는 left child node 로 움직이면 되고,
- Max Node Boundary 보다 큰 key 에 대해서는 right child node 로 움직이면 되며
- 이 사이에 있는 key 들은 저 Data Pointer 를 이용해 접근할 수 있는 것이다.
- 근데 이놈은 좀 문제가 있다.
- 일단 AVL tree 처럼 child 간의 height 를 기준으로 rebalancing 을 하기 때문에, SMO 비용이 크다.
- 그리고 pointer 여러개를 atomic 하게 바꿔야 하기 때문에, latch-free 로 설계하기가 힘들다.
BwTree (OpenBwTree, SIGMOD’18)
내용 옮겨짐
Evaluation
- 하지만 OpenBwTree 논문의 핵심은 이렇게 latch 를 다 없앤다고 하더라도 performance 가 그리 좋지는 않다는 것이다.
- 즉, 기존의 BwTree 논문에서는 성능이 잘 나온다고 했었는데, 이 OpenBwTree 에서는 논문에 나온 대로 구현했더니 성능이 별로였고, 이에 따라 delta node 들을 pre-allocate 해서 base node 들에 inlining 하는 등의 optimization 을 해도 성능이 별로였다는 것이다.
- 즉, 위의 그림에서 보이는 것 처럼 성능이 그리 잘 나오지는 않는다.