B-Tree

인덱스의 자료구조

해시 테이블 (Hash Table)

• 해시 테이블은 Key와 Value를 한 쌍으로 데이터를 저장하는 자료구조입니다. (key, value)로 쌍을 표현하며 key값을 이용해 대응되는 value값을 구하는 방식입니다.

• 해시 충돌이라는 변수가 존재하지만 평균적으로 O(1)의 매우 빠른 시간만에 원하는 데이터 탐색을 할 수 있는 구조입니다.

• 해시 테이블을 이용한다면 인덱스는 (key, value) = (컬럼의 값, 데이터의 위치)로 구현되는데, 해시 테이블은 실제로 인덱스에서 잘 사용되지 않습니다.

• 해시 테이블은 등호(=) 연산에 최적화 되어있기 때문입니다. DB에선 부등호(<, >) 연산이 자주 사용되는데 해시 테이블 내의 데이터들은 정렬되어 있지 않으므로 특정 기준보다 크거나 작은 값을 빠른 시간내에 찾을 수가 없습니다.

B-Tree

• 트리 구조는 꼭 데이터베이스에 한정하지 않더라도 시스템 세계에서는 데이터를 유지하기 위해 자주 사용되는 구조입니다. “탐색"시 단시간 내에 실행할 수 있기 때문입니다.

• B-Tree의 핵심은 데이터가 정렬된 상태로 유지되어 있다는 점 입니다.

• 위의 표시된 사각형으로 표시된 한개 한개의 데이터를 노드(Node)라고 합니다.
• 가장 상단의 노드를 “루트 노드”, 중간 노드를 “브랜치 노드”, 가장 아래 노드들을 “리프노드"라고 합니다.

• B-Tree는 Binary Search Tree와 유사하지만 한 노드 당 자식 노드가 2개 이상이 가능합니다.

• key 값을 이용해 찾고자 하는 데이터를 트리 구조를 이용해 찾는 것입니다.

B-Tree는 왜 빠를까?

• B-Tree의 장점 한 가지는 “어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다"이며 이를 균일성이라고 합니다.

• 위의 예시에서 리프노드에 있는 15, 21, 26, 28, 42… 등등 찾는 시간은 동일할 것입니다.
• 트리 높이가 다른 경우 차이가 있겠지만 O(logN)이라는 시간 복잡도를 가집니다.

• 만약 선형탐색일 경우 해당 값을 찾기 위해 배열을 하나씩 체크하는 방법밖에 없으며 시간은 더 소모됩니다.

균형트리?

• 균형트리란 루트로부터 리프까지의 거리가 일정한 트리 구조를 뜻하는 것으로 트리 중에서 특히 성능이 안정화 되어 있습니다.

• 그러나 B-Tree 처음 생성 당시 균형 트리이지만 테이블 갱신(INSER, UPDATE, DELETE)의 반복을 통해 서서히 균형이 깨지고 성능도 악하됩니다.

• 어느정도 자동으로 균형을 회복하는 기능이 있지만, 갱신 빈도가 높은 테이블에 작성되는 인덱스 같은 경우 인덱스 재구성을 해서 트리의 균형을 되찾는 작업이 필요합니다.

• 풀 스캔이 테이블 크기에 비례하는 형태로 실행 시간이 들어가는데에 비해 인덱스를 사용한 경우 실행 시간의 저하는 원만한 곡선을 그리게 됩니다.

B+Tree

• 기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 비효율 적입니다. 따라서 B-Tree의 단점을 개선시킨 자료구조가 B+Tree입니다.

• B+Tree는 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장합니다. 그리고 left node끼리는 Linked List로 연결되어 있습니다.

• B+Tree 에서는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있습니다.

B+Tree를 사용한 장점

• 리프노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key를 수용할 수 있습니다.
• 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더욱 낮아집니다.(cache hit를 높일 수 있음)

• 풀 스캔시 B+Tree는 리프노트에 데이터가 모두 있기 때문에 한번의 선형탐색만 하면 되기 때문에 B-Tree에 비해 빠릅니다.
• B-Tree의 경우에는 모든 노드를 확인해야 합니다.

InnoDB에서 사용된 B+Tree

• 같은 레벨의 노드들끼리 Linked List가 아닌 Double Linked List를 사용했으며 자식 노드로는 Single Linked List로 연결되어 있습니다.

• key의 범위마다 찾아가야할 페이지 넘버(포인터)가 있는데, 해당 페이지 넘버를 통해 다음 노드로 넘어가게 됩니다.

• 리프 노드에 다다랐을때 디스크에 존재하는 데이터의 주소값을 구할 수 있고, Linked List를 통해 탐색도 가능합니다

B-Tree VS B+Tree

REF

[MySQL] B-tree, B+tree란? (인덱스와 연관지어서)

B-tree는 인덱스를 이루고 있는 자료구조의 일종이다. B-tree에서 'B'는 정확히 어떤 의미라고 밝혀진 바는 없다. 아마 'Balanced'를 의미하는 'B'가 아닐까라는 추측만 있다. MySQL의 DB engine인 InnoDB는 B+tree 로 이뤄져있는데, B-tree의 확장된 개념 이다. 먼저 B-tree 를 살펴보자. 트리 구조의 우위성 트리 구조는 꼭 데이터베이스에 한정하지 않더라도 시스템 세계에서는 데이터를 유지하기 위해 자주 사용하는 구조이다.

https://zorba91.tistory.com/293