B tree 계열의 시간 복잡도
의문사항 B tree와 Self-balancing BST의 빅O가 동일한데 무슨 차이가 있는 것일까? 이에 대한 대답을 위해서는 컴퓨터 시스템에 대한 이야기를 해야한다. DB는 Secondary Storage에 저장된다.
컴퓨터 시스템 간략 리뷰
2ndary storage 특징
DB 관점에서 지금까지 내용 정리
인덱스로 성능 비교 전에 몇 가지 가정
AVL tree 인덱스로 조회하기
5차 B tree 인덱스로 조회하기
왜 5차 B tree 인덱스가 더 성능이 좋은가?
storage 접근 횟수, 자녀 노드 수, 노드의 데이터 수가 차이를 만든다.
B tree의 강력함 (feat. 101차 B tree)
101차 B tree best case의 데이터 총 수
101차 B tree worst case의 데이터 총 수
101차 B tree avg case의 데이터 총 수
결론 : B tree 계열을 DB 인덱스로 쓰는 이유
번외
self-balancing BST도 튜닝한다면..?
hash index를 쓰면 더 좋지 않나?
Engineer, Look Beyond the Code.