https://steady-coding.tistory.com/558
b+트리는 innodb의 데이터 저장 자료구조로 사용되고 있다.
b+트리는 항상 o(nlogn)의 시간 복잡도를 가지므로 검색 성능이 일반 트리는 일반적인 경우 o(logn)의 성능을 내지만, 최악의 경우 o(N) 성능을 가진다. 최악의 경우를 방지하기 위해 b+트리를 사용한다.
b+트리는 leaf노드에 데이터를 저장한다. leaf노드는 각 leaf노드들끼리의 링크드 리스트 형태로 저장된다.
검색에는 빠르지만, 삽입과 삭제 시 밸런스를 맞추기 위한 리밸런싱이 이뤄지면서 일반 트리보다 성능이 낮다.
vs 리스트
모든 데이터가 메모리 상 차례대로 저장되어 있으므로 배열의 인덱스를 통해 O(1)의 시간 복잡도로 요소를 조회할 수 있다. 참조가 없으니 당연히 탐색 속도로는 B-Tree보다 훨씬 빠르다. 그리고 해시 테이블은 아래에서 자세히 다루겠지만, 해시 테이블과는 다르게 데이터를 정렬 상태로 유지할 수 있으므로 부등호 연산에도 문제가 없다.
하지만 배열이 B-Tree보다 빠른 것은 오직 탐색 뿐이다. 배열 내에서 데이터의 저장이나 삭제가 일어나는 순간 B-Tree보다 훨씬 성능이 떨어진다.
>> 모든 데이터를
vs 해시
해시 테이블은 해시 함수를 통해 나온 해시 값을 이용하여 저장된 메모리 공간에 한 번에 접근하므로 O(1)이라는 시간 복잡도를 갖는다. 물론 해시 충돌 등으로 최악의 경우에는 O(N)이 될 수 있지만, 평균적으로는 O(1)이다.
그러나 이는 온전히 단 하나의 데이터를 탐색하는 시간에만 O(1)이다. 만약, 부등호 연산을 사용하게 된다면 어떻게 될까?
해시 테이블은 모든 값이 정렬되어 있지 않으므로 특정 기준보다 크거나 작은 값을 찾을 수 없다. 굳이 찾으려면 가능하겠지만 O(1)의 시간 복잡도를 보장할 수 없고 매우 비효율적이다. 그렇기에 기준 값보다 크거나 작은 요소를 탐색할 수 있어야 하는 DB 인덱스 용도로 해시 테이블은 적합하지 않은 것이다.
다만, 등호 연산에서 해시 테이블은 훌륭한 성능을 자랑하므로 특정 경우에만 해시 인덱스를 적용하여 사용할 때도 있다. 이것은 다음 포스팅에서 설명하려고 한다.