인덱스 바이너리

마지막 업데이트: 2022년 1월 10일 | 0개 댓글
  • 네이버 블로그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 트위터 공유하기
  • 카카오스토리 공유하기
B-Tree 와 Binary Tree 가 어떻게 다른지

인덱스 바이너리


이진탐색 (Binary Search) 알고리즘.

N 개의 데이터를 가진 배열 list[] 가 있고 , 우리가 찾고자 인덱스 바이너리 하는 값이 key 라고 하자 ( list[0], list[1], . list[N-1] ).

이진 탐색은 배열의 중간요소 (list[N/2]) 와 찾고자하는 값 (key) 을 비교한다 . 찾고자하는 값이 중간요소 보다 작다면 배열의 중간요소 보다 큰 요소들 (list[N/2] . list[N-1]) 에는 찾고자 하는 데이터가 없는 것이다 . 즉 , 데이터의 절반은 검사 할 필요가 없어진다 .

나머지 요소들에 인덱스 바이너리 대해 똑같이 반복한다 . (Recusive)

탐색방법
입력 : 리스트,시작인덱스,마지막인덱스,검색값

출력 : 해당 키의 인덱스 ( 찾는 값이 있으면 ) 또는 아니오 ( 찾는 것이 없으면)

head : 찾고자 하는 리스트 의 처음
tail : 찾고자 하는 리스트의 끝
mid : head 와 end의 중간 값

2. 리스트의 중간에 있는 원소의 키(list[mid]) 와 탐색하려는 값 key를 비교

| 1. 중간요소를 구한다 . mid = (head + tail ) / 2 |

| 2. 중간요소보다 key 값이 크면 , mid 를 head 로 한다 . |

| 3. 중간요소보다 key 값이 작으면 , mid 를 tail 로 한다 . |

| 5. 중간요소와 key 가 같으면 찾았음 , 그렇지 않으면 찾지 못함 . |

| 24 | 36 | 37 | 45 | 57 | 61 | 69 | 81 | 95 |

[0] [1] [2] [3] [4] [5] [6] [7] [8]

mid = (head + tail) / 2

2) 중간요소보다 key 값이 크면 , mid 를 head 로 하고 , 중간요소를 구한다 .

| 24 | 36 | 37 | 45 | 57 | 61 | 69 | 81 | 95 |

[0] [1] [2] [3] [4] [5] [6] [7] [8]

mid = (head + tail) / 2

3) 중간요소보다 key 값이 작으면 , mid 를 tail 로 하고 , 중간요소를 구한다 .

| 24 | 36 | 37 | 45 | 57 | 61 | 69 | 81 | 95 |

[0] [1] [2] [3] [4] [5] [6] [7] [8]

mid = (head + tail) / 2

4) 중간요소 = key. 찾았음

| 24 | 36 | 37 | 45 | 57 | 61 인덱스 바이너리 | 69 | 81 | 95 |

[0] [1] [2] [3] [4] [5] [6] [7] [8]

이 이진 탐색 알고리즘은 간단하면서도 무척 빠르다 . 이진 탐색의 인덱스 바이너리 큰 단점은 소트된 데이터에만 적용이 가능하다는 점이다 . 따라서 , 이진탐색을 하기전에 반드시 소트 를 해야만 한다 .

수시로 데이터가 입력되고 조회되어야 하는 온라인 (on-line) 시스템에서 이진 탐색을 사용한다는 것은 힘든 일이다 . 데이터가 입력 될때 마다 소트를 해야하기때문이다 . 그러나 , 수집된 데이터를 하루 혹은 일주일 단위로 한꺼번에 처리하는 일괄처리 (batch) 작업에서는 아주 좋은 효과를 볼수있다 .

인덱스 바이너리

이진 탐색은 정렬된 배열에서 특정 값을 찾을 때 사용 한다. 탐색 범위의 가운데 지점에 있는 값을 기준으로 찾고자 하는 값이 더 작으면 왼쪽 범위로, 더 크면 오른쪽 범위로 탐색 범위를 좁혀 가는 것이 핵심 이다. 분할 정복 알고리즘의 대표적인 예이며, 인덱스 바이너리 탐색 시간 복잡도는 O(logN)이다.

위와 같이 정렬된 배열이 있고, 10을 찾는다고 가정해 보자. (밑에 작은 숫자는 배열의 인덱스이다.)

축소된 범위에서 가운데 지점(5번 인덱스 = (4+6)/2)에 있는 값은 11(>10)이므로, 왼쪽 범위로 탐색의 범위를 축소한다.

축소된 범위에서 가운데 지점에 있는 값은 10이므로, 찾고자 하는 값은 배열의 4번 인덱스에 있음을 알 수 있다. 특정 값을 탐색할 때 더 이상 범위를 좁힐 수 없는 상황이 되면, 해당 배열에 찾고자 하는 값이 없다고 판단하면 된다.

위 코드는 반복문 베이스로 구현한 이진 탐색 예시이다. 탐색 대상 배열과 그 인덱스 바이너리 배열의 시작과 끝 인덱스, 그리고 탐색하고자 하는 값을 매개변수로 전달 받아, 그 값이 위치한 배열의 인덱스를 반환한다. 만약 배열에 없는 값이면 -1을 반환한다.인덱스 바이너리

38. Binary Search

이분 탐색(이진 탐색, Binary Search) 은 정렬된 데이터에서 원하는 값을 빠르게 찾을 수 있는 탐색 방법이다. 기본적인 원리는 정렬된 데이터를 앞쪽 절반과 뒤쪽 절반으로 나눈 다음 두 구간 중 해당 값을 포함하지 않는 구간을 배제하고 남은 한 구간에서 다시 데이터를 찾는 과정을 반복하는 것이다. 이렇게 하다가 구간에 값이 하나 남았을 경우 그 값을 찾는 값과 비교해서 같다면 원하는 값을 찾은 것이고, 다르다면 데이터에 원하는 값이 존재하지 않는 것이다. 데이터의 수가 $n$일 때 이분 탐색의 시간복잡도는 $O(\textn)$ 이다.

이 문제를 통해서 이분 탐색을 더 자세히 이해할 수 있다. 일단 $n$개의 정수를 정렬하고, 찾으려는 각각의 값이 $n$개의 정수 중에 존재하는지를 이분 탐색으로 확인하면 된다.

원리는 쉽지만, 구현 시 주의해야 할 부분이 존재한다.

이분 인덱스 바이너리 탐색의 구현을 위해서는 데이터의 양 끝과 중간 위치를 저장할 세 개의 변수가 필요하다. (이 변수들이 '값' 자체가 아닌 값의 '위치'를 저장한다는 사실을 헷갈리지 않아야 한다) 일반적으로 데이터의 처음을 가리키는 변수$(l)$는 첫 번째 원소의 인덱스를 저장하기 때문에 별로 문제가 되지 않지만, 데이터의 끝을 가리키는 변수$(r)$는 마지막 원소의 인덱스를 저장할 수도 있고 마지막 원소 다음의 인덱스를 저장할 수도 있다. $r$이 저장하는 값에 따라서 찾으려는 데이터가 존재할 수 있는 인덱스 구간이 $[l, r]$이 될 수도 있고 $[l, r)$이 될 수도 있으므로 구현 시 둘 중 어떤 방법을 사용할지를 확실하게 정해야 한다.

다음으로 데이터의 중간 위치를 가리키는 변수$(m)$이 어떤 인덱스를 가리키게 할지를 결정해야 한다. 만약 $l$과 $r$의 홀짝이 같다면 단순히 $m=(l+r)/2$로 두면 문제가 없다. $l$과 $r$의 홀짝이 다를 경우가 문제인데, 이 경우 구간의 정중앙이 하나로 결정되지 않기 때문에 가운데에 있는 두 인덱스 중 어느 한쪽을 $m$으로 하게 된다. 왼쪽을 $m$으로 할 경우 $m=(l+r)/2$로, 오른쪽을 $m$으로 할 경우 $m=(l+r+1)/2$로 두면 된다.

또한 $m$을 정하는 방법에 따라 구간을 나누는 방법도 달라진다. $m=(l+r)/2$인 경우 나누어지는 두 구간은 $[l, m]$과 $[m+1, r]$(또는 $[m+1, r)$)이 되고, $m=(l+r+1)/2$인 경우 $[l, m-1]$과 $[m, r]$(또는 $[m, r)$)이 된다. 이런 차이는 두 구간의 크기 차이를 최소화해야 하기 때문에 발생한다. 더 정확한 목적은 크기가 $0$인 구간이 생기지 않게 하는 것이다. 구간을 잘못 나눠서 두 구간 중 하나의 크기가 $0$이 될 경우 탐색이 끝나지 않는 문제가 발생할 수 있다.

이것들을 모두 고려해서 구현한 이분 탐색 코드는 다음과 같다. $r$은 구간의 마지막 원소의 인덱스를 가리킨다. 찾는 수는 $k$이다.

반복이 끝난 후 $a[l]$이 $k$와 같다면 $k$의 위치를 찾은 것이고, 다르다면 데이터에 $k$가 없는 것이다. 이때 마지막 비교에 $a[l]$ 대신 $a[r]$을 써도 결과는 같지만 $a[m]$을 쓰면 결과가 달라질 수 있으므로 주의해야 한다.

만약 $r$이 구간의 마지막 원소 다음의 인덱스를 가리킬 경우 나머지는 그대로 두고 반복의 조건만 $l+1

위에서 언급한 주의할 점들 때문에 이분 탐색의 구현에 익숙하지 않을 경우 실수하기 쉽다.

위의 두 코드는 특정한 상황에서 반복이 끝나지 않게 된다. $l+1=r$인 경우 $m=l$이 되고, 비교를 통해서 $l=m;$ 문장이 실행될 경우 반복 후 $l$과 $r$ 중 어느 값도 변하지 않는다. 따라서 무한루프가 발생한다. $m$을 $(l+r+1)/2$로 설정하더라도 $r=m;$ 문장이 실행되면 반복 후 $l$과 $r$이 모두 그대로인 것은 마찬가지이다. 이 상황을 막기 위해서 인덱스 바이너리 $a[m]$이 $k$와 같은 경우를 먼저 따로 처리한다고 해도 반복이 끝나지 않을 가능성이 여전히 존재한다. 실수하기 좋은 코드이므로 주의할 필요가 있다.

정확한 이분탐색 코드를 작성한 다음 찾으려는 각각의 수에 대해서 실행하면 위의 문제를 해결할 수 있다. 이 문제의 경우 매우 전형적이지만 실수하기 좋은 부분이 많으므로 꼼꼼한 확인이 필요하다.

1. $n$개의 정수를 정렬하는 과정에서 문제가 생기는 경우
A) $n$의 최대값이 $10$만이므로 시간복잡도가 $O(n^2)$인 정렬 방법을 이용할 경우 데이터가 약하지 않다면 당연히 시간 초과 가 발생한다.
B) 퀵 정렬을 직접 구현할 경우 모든 입력에 대해 좋은 피벗을 정하는 것이 쉽지 않다. 다양한 저격 데이터가 존재하면 시간 초과 가 발생할 가능성이 매우 높다. 피벗을 정할 때 무작위적인 요소를 넣으면 느려지는 문제를 일부 해결할 수는 있다.
C) 병합 정렬을 직접 구현할 경우 배열의 재할당이나 vector의 복사 처리를 잘못하면 시간 초과 , 런타임 에러 , 메모리 초과 등의 결과가 나올 수 있다.

2. 입출력이 느린 경우
D) C++의 cin, cout을 그냥 사용할 경우 시간 초과 가 발생할 수 있다. cin, cout의 입출력 속도가 느리기 때문이며, 이때는 ios_base::sync_with_stdio(0);과 cin.tie(0);을 main함수 시작 부분에 추가해야 한다. 단 이것을 추가하면 cin, cout 계열의 입출력과 scanf, printf 계열의 입출력 중 하나만 일관적으로 사용해야 한다. 두 계열의 입출력을 같이 사용하면 작동 순서가 엉망이 될 수 있다.
E) 줄바꿈을 endl로 처리해서 시간 초과 가 발생할 수도 있다. endl이 출력 버퍼를 매번 비우기 때문에 느려지는 것이며, 이때는 endl 대신 '\n'을 사용해야 한다.

3. 오버플로우가 발생하는 경우
F) $4$바이트 정수 자료형을 사용하고 $l+r$을 계산하거나 $l$과 $r$의 대소 비교를 $r-l$과 같은 방식으로 하는 경우 오버플로우가 발생할 수 있으며 이때는 $8$바이트 정수 자료형을 사용하면 된다. $4$바이트 정수 자료형으로도 조금 복잡한 방법으로 해결은 가능하지만 그렇게까지 해야 할 이유가 딱히 없다.

4. 이분 탐색의 구현이 잘못된 경우
G) $l==r$일 때 반복을 끝내는 방식으로 구현하면 시간 초과 가 발생할 수 있다. 구현 방식에 따라 반복 중간에 $l>r$이 되는 경우도 존재할 수 있으므로 $l>=r$일 때 반복을 끝내는 방식으로 구현하는 것이 좋다.
H) 이분 탐색 과정에서 한 번의 반복 후에는 $l$과 $r$ 중 최소한 하나의 값이 변한다는 것이 보장되어야 한다.

이분 탐색은 단독으로 쓰이는 경우는 생각보다 많지는 않고 나중에 소개할 Parametric Search의 일부로 사용되는 경우가 많다.

인덱스 바이너리

인덱스는 우리가 흔히 아는 색인이라고 생각을 하면 이해가 조금더 빠를 수 있다가. 가나다 순이고 키워드가 같을 땐 페이지 순으로 찾는다. 이처럼 좀 빨리 찾고 싶을 때 우리가 색인을 이용하는 것처럼 데이터 베이스도 인덱스로 DBMS 도 찾는다. root 노드가

인덱스 기본 구조의 노드는 -> B* Tree 가 일반적.이다. 이 처럼 정말 나무를 뒤집어 놓았으므로 맨 위쪽 뿌리를 설정해줄 수 있으며 해당 루프, 브랜치 , 리프까지 모두 갖춘 노드를 의미한다.

ROWID : 테이블 레코드를 찾아가기 위해 필요한 주소 정보

키 값이 같을 경우에는 ROWID 순으로 정렬된다는 사실 ~~

이는 정방향 스캔과 역방향 스캔이 둘다 가능하도록 양방향 연결 리스트 ( Double Linked List) 구조로 연결함.

B-Tree 와 Binary Tree 가 어떻게 다른지

B-Tree 와 Binary Tree

* B- Tree : 자식 노드의 개수가 2개 이상인 트리를 말함. 또한 이처럼 위의 부모 노드는 자식의 노드를 정렬시키는 기준이 되며 노드 기준보다 데이터가 작은 값은 왼쪽에~ 그리고 데이터가 큰 값은 오른쪽에 위치 된다.

  • B-tree: stores keys in its internal nodes but doesn’t need to store those keys in the records at the leaves.
  • B+ tree: copies of the keys are stored in the internal nodes while the keys and records are stored in leaves; in 인덱스 바이너리 addition, a leaf node may include a pointer to the next leaf node which speeds the sequential access.
  • B* tree: keep the internal nodes more densely packed by balancing more neighbouring internal nodes. This ensures non-root nodes are fuller – 2/3 instead of 1/2.

* 인덱스 리프 블록에 저장된 레코드 끼리 연결된 순서에 따라 좌에서 우 또는 우에서 좌로 스캔

* 루트에서 리프 블록까지 아래쪽으로 진행하기 때문에 수직적이다.

인덱스 바이너리

우선 ) B+Tree 와 B* Tree 에 대해서 몇가지 조건이 존재.

인덱스와 키가 존재하고 해당 조건이 몇개의 키까지 하나의 노드에 저장되는지 정해진다.

해당 노드가 우선 정해지고 그다음에 삽입이 되거나 삭제가 될 때 몇가지 rule 에 따라 움직인다.

B+ 성립 조건에 따라서 삽입이 된다.

* 노드의 데이터수가 n개라면 자식 노드의 개수는 n+1 개

* 노드의 데이터는 반드시 정렬된 상태

* 노드의 자식노드의 데이터들은 노드 데이터를 기준으로 데이터보다 작은 값은 왼쪽 서브 트리에 큰값들은 오른쪽 서브 트리

* Root 노드가 자식이 있다면 2개이상의 자식

* Root 노드를 제외한 모든 노드는 적어도 M/2 개의 데이터를 가져야 함. 3차 인덱스 바이너리 B-Tree 는 1 개의 노드 / 4 차 B-Tree 는 2개 이상의 노드를 가져야함.

* Leaf 노드로 가는 경로의 길이가 같아야함. Leaf 노드는 모두 같은 레벨에 존재

정말 B Tree 에 대해서 잘 설명한 것 같은 블로그 링크!

데이터베이스와 파일시스템에서 B-Tree를 많이 사용합니다. rdb 인덱스 관련해서 정리해보다가 일반적으로 B-Tree , B+-Tree 자료구조를 사용하는것을 알게되었습니다. B-Tree 자료 구조에 대해서 알아

[MySQL] B-Tree 인덱스

인덱스는 데이터베이스 쿼리의 성능을 언급하면서 빼놓을 수 없는 부분입니다. MySQL에서 사용 가능한 인덱스의 종류 및 특성에서 각 특성의 차이는 상당히 중요하며, 물리 수준의 모델링을 할

인덱스 바이너리

배열 내의 특정 값을 찾는 기초적인 알고리즘이다. 특정 값을 찾기 위해 모든 데이터를 순차 탐색을 하는 것이 아니라 탐색 범위를 반씩 줄여나가며 탐색을 진행한다는 특징을 가지고 있다. 여기서 중요한 점은 배열이 정렬되어 있어야 한다는 점이다. 특정 조건을 토대로 범위를 절반씩 줄여나가기 때문에 정렬되지 않은 배열에서 이분 탐색은 사용할 수 없다.

이분 탐색을 구현할 때 변수를 보통 세 가지를 사용한다. start, mid, end 세 가지 변수를 통해 현재 탐색 범위의 시작은 start, 탐색 범위의 끝은 end, 그 중간 값은 mid로 사용한다.(물론 변수 명은 개인에 따라 바뀔 수 있다). 이 세 변수를 통해 찾으려는 데이터와 중간 값 위체에 있는 데이터를 반복적으로 비교해서 특정 값을 찾는 것이 이분 탐색이다.

예시

정렬되어 있는 배열 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]에서 7이라는 값을 이분 탐색으로 찾아보도록 하자. 탐색하려는 구간의 시작 인덱스는 0이고 끝 인덱스는 9다. 구간 시작을 뜻하는 start 변수에는 0, 구간 끝을 뜻하는 end 변수에는 9, 그 중간값을 뜻하는 mid 변수에는 (0+9)/2 값인 4를 넣도록 하겠다. 그럼 이제 4번 인덱스의 값을 확인해보도록 하자.

start: 0, mid: 4, end: 9

우리가 찾으려는 값은 7이지만 4번 인덱스에 들어있는 값은 5다. 우리가 찾으려는 값은 찾지 못했지만 우리는 중요한 정보를 얻을 수 있다. 바로 7은 4번 인덱스 이후에 오는 값이라는 것이다. 이분 탐색이 이루어지는 배열은 정렬된 배열이기 때문에 4번 인덱스보다 작은 인덱스에 있는 값들은 모두 5보다 작은 값이라는 것을 알 수 있기 때문이다. 그렇다면 이번에는 start값을 4번 인덱스에 1 더한 값으로 설정하자. mid는 자연스럽게 (5+9)/2 값인 7이 된다.

start: 5, mid: 7, end: 9

7번 인덱스의 값은 8이다. 7과 비교했을 때 8은 크기 때문에 7번 인덱스 이후에 오는 값들은 무조건 7보다 큰 값이 될 것이다. 그렇다면 7번 인덱스와 그 이후 인덱스 값들은 제외하고 탐색을 진행한다. 이번에는 end 변수 값을 바꿔야 한다. 7에서 1 줄인 값인 6을 넣어보자. mid 역시 (5+6)/2 값인 5가 된다.

start: 5, mid: 5, end: 6

5번 인덱스의 값은 6, 7보다 작으니 start는 mid에 1을 더한 6이 되고 mid 또한 6이 된다.

start: 6, mid: 6, end:6

6번 인덱스 값이 우리가 찾던 7인 것을 확인할 수 있다. 지금까지 인덱스 바이너리 단 네 번의 탐색만으로 6번 인덱스의 값을 찾아내는 것을 직접 확인했다. 만일 순차 탐색을 통해 6번 인덱스의 7을 찾고자 했다면 7번의 탐색이 필요했다. 3번 인덱스 바이너리 차이라 조금 와닿지 않을 수 있다. 그렇다면 이렇게 생각해보자.

우리가 크기가 10인 배열에서 9번 인덱스에 있는 10을 찾는다고 해보자. 순차 탐색이라면 10번을 탐색해야 한다. 이분 탐색은 4번의 탐색이 필요하다. 만일 이 배열의 크기가 두배로 늘어난다고 해보자. 인덱스 19번에 있는 20이라는 숫자는 순차 탐색으로 20번 탐색해야 인덱스 바이너리 한다. 기존 탐색 횟수에서 두배가 늘어났다. 하지만 이분 탐색은 기존 탐색 횟수에서 단 1번밖에 늘어나지 않은 5번의 탐색이면 20을 찾을 수 있다. 한 번의 탐색으로 0번부터 9번까지 인덱스는 탐색하지 않아도 된다는 것을 확인할 수 있기 때문이다.

위와 같은 탐색방법을 코드로 구현하면 다음과 같다.

예시 문제

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

참고

[알고리즘] 이분 탐색 / 이진 탐색 (Binary Search)

이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는


0 개 댓글

답장을 남겨주세요