[index] B+-Tree, Hash Table

이번에는 인덱스에 관련돼서 정리해보려고 합니다.

간단하게 설명하자면 단어를 찾아보기 위해 백과사전을 보고 있다고 생각해봅니다. 이때 특정 단어를 검색해보기 위해 책장을 무수히 넘겨봅니다. 한 번은 이렇게 찾는다 쳐도 수 백번, 수 천 번 그런다면 정말 비효율적이겠죠? 이럴 때 필요한 게 목차입니다. 특정 단어의 위치를 목차에서 보고 위치를 유추할 수 있습니다. 이 역할을 하는 게 바로 인덱스입니다.

 

  

데이터베이스에서 인덱스란?

테이블에 대한 동작(검색)의 속도를 높여주는 자료 구조를 뜻합니다. 인덱스는 테이블 내의 1개의 컬럼, 혹은 여러 개의 컬럼을 이용하여 생성될 수 있습니다. 고속의 검색 동작뿐만 아니라 레코드 접근과 관련 효율적인 순서 매김 동작에 대한 기초를 제공합니다. 인덱스를 저장하는 데 필요한 디스크 공간은 보통 테이블을 저장하는 데 필요한 디스크 공간보다 작습니다. (왜냐하면 보통 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목들은 갖고 있지 않기 때문입니다.)

 

 

인덱스의 자료구조

 

1. Hash Table

해시 테이블은 데이터 요소의 주소/인덱스 값이 해시 함수에서 생성되는 데이터 구조 유형입니다. 인덱스 값이 데이터 값에 대한 키로 동작하므로 매우 빠른 데이터 액세스가 가능합니다.

즉, 해시 테이블은 키-값 쌍을 저장하지만 키는 해싱 함수를 통해 생성됩니다. 따라서 키 값 자체가 데이터를 저장하는 배열의 인덱스가 되기 때문에 데이터 요소의 검색 및 삽입 기능이 훨씬 빨라집니다. 조회하는 동안 키가 해시되고 결과 해시는 해당 값이 저장된 위치를 나타냅니다.

 

해싱의 개념은 버킷 배열에 항목(키/값 쌍)을 배포하는 것입니다. 키가 주어지면 알고리즘은 항목을 찾을 수 있는 위치를 제안하는 인덱스를 계산합니다. 해시 테이블의 시간 복잡도는 O(1)이며 매우 빠른 검색을 지원합니다. 하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그러한 이유는 해시가 등호(=) 연산에만 특화되었기 때문입니다. 해시 함수는 값이 조금이라도 달라지면 완전히 다른 해시 값을 생성합니다. 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않습니다.

 

2.B-Tree

출처:http://www.btechsmartclass.com/data_structures/b-trees.html

B-트리는 모든 노드가 여러 키를 포함하고 2개 이상의 자식을 갖는 자체 균형 탐색 트리입니다.

 

B-Tree의 다음과 같은 속성을 가지고 있습니다.

• 모든 리프 노드는동일한 수준에 있어야 합니다.
• 루트를 제외한 모든 노드에는 최소 [m/2]-1개의 키와 최대 m-1개의 키가 있어야 합니다.
• 루트를 제외한 모든 비 리프 노드(즉, 모든 내부 노드)에는 최소 m/2개의 자식이 있어야 합니다.
• 루트 노드가 리프 노드가 아닌 경우 최소 2개의 자식 이 있어야 합니다.
• n-1개의 키가 있는 비 리프 노드에는 n개의 자식이 있어야 합니다.
• 노드의 모든 키 값은 오름차순 이어야 합니다.

B-Tree에서 검색 작업

B-Tree의 검색 작업은 이진 검색 트리의 검색 작업과 유사합니다. 이진 탐색 트리에서 탐색 프로세스는 루트 노드에서 시작하고 매번 양방향 결정을 내립니다(왼쪽 하위 트리 또는 오른쪽 하위 트리로 이동). B-Tree에서도 검색 프로세스는 루트 노드에서 시작되지만 여기에서는 매번 n-way 결정을 내립니다. 여기서 'n'은 노드가 가진 총 자식 수입니다. B-Tree에서 탐색 연산은 O(log n) 시간 복잡도로 수행됩니다. 검색 작업은 다음과 같이 수행됩니다.

• 1단계 - 사용자로부터 검색 요소를 읽습니다.
• 2단계 - 검색 요소를 트리에서 루트 노드의 첫 번째 키 값과 비교합니다.
• 3단계 - 둘 다 일치하는 경우 "주어진 노드를 찾았습니다!!!"를 표시합니다. 함수를 종료하고
• 4단계 - 둘 다 일치하지 않으면 검색 요소가 해당 키 값보다 작거나 큰지 확인합니다.
• 5단계 - 검색 요소가 더 작은 경우 왼쪽 하위 트리에서 검색 프로세스를 계속합니다.
• 6단계 - 검색 요소가 더 크면 검색 요소를 동일한 노드의 다음 키 값과 비교하고 정확히 일치하는 항목을 찾거나 검색 요소가 마지막 키 값과 비교할 때까지 3, 4, 5, 6단계를 반복합니다. 잎 노드.
• 7단계 - 리프 노드의 마지막 키 값도 일치하지 않으면 "요소를 찾을 수 없음"을 표시하고 기능을 종료합니다.

B-트리의 삽입 작업

B-Tree에서는 리프 노드에만 새 요소를 추가해야 합니다. 즉, 새 keyValue는 항상 리프 노드에만 연결됩니다. 삽입 작업은 다음과 같이 수행됩니다...

• 1단계 - 트리가 비어 있는지 확인합니다.
• 2단계 - 트리가 비어 있는 경우 새 키 값으로 새 노드를 만들고 트리에 루트 노드로 삽입합니다.
• 3단계 - 트리가 비어 있지 않은 경우 이진 검색 트리 논리를 사용하여 새 키 값이 추가되는 적절한 리프 노드를 찾습니다.
• 4단계 - 해당 리프 노드에 빈 위치가 있는 경우 노드 내 키 값의 오름차순으로 해당 리프 노드에 새 키 값을 추가합니다.
• 5단계 - 해당 리프 노드가 이미 가득 찬 경우 중간 값을 상위 노드로 전송하여 해당 리프 노드를 분할합니다.보내는 값이 노드에 고정될 때까지 동일한 작업을 반복합니다.
• 6단계 - 루트 노드에서 분할이 수행되면 중간 값이 트리의 새 루트 노드가 되고 트리의 높이가 1 증가합니다.

2.B+Tree

B+Tree는 B-Tree의 개념을 조금 더 확장한 것입니다. B+tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않지 않습니다. 오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있습니다. 

 

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

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

결론

인덱스를 사용하면 풀스캔보다 일정 데이터양 이후 처리시간이 비슷해지는 것을 볼 수 있습니다. 풀 스캔인 경우 데이터양에 비례합니다. 

인덱스의 장점으로는 앞에서 말했다시피 테이블의 검색 속도와 성능이 향상됩니다. 하지만, 단점으로 인덱스를 관리하기 위한 추가 작업과 별도의 저장공간이 필요합니다. 인덱스를 잘못 사용할 경우 오히려 성능이 저하될 수 있습니다. 소규모 테이블에서는 풀스캔이 빠를 수 있고, 대용량 테이블에서는 인덱스를 사용하면 성능 향상을 기대해볼 수 있습니다.