인덱스 바이너리

디비인덱스 개념이 바이너리 서치인가요?

디비의 인덱스 개념하고 컴언어(자바쪽)의 binary 서치가 같은 개념
이라고 제가 우연히 설명을 드렸습니다.

그러면서 제가 O(log n) 이정도 퍼포먼스를 보장한다 이렇게 말하면서
기하급수적으로 서치타임(걸리는 시간)이 걸리지 않고
지수적으로 서치타임이 걸린다 이렇게 설명하고
-- 데이터가 아무리 많아져서 서치타임은 어느정도 범위 내에 수렴한다
전 이런 의미로 파악했네요 (지수적 기하급수적)

바이너리 서치 하기전에 해당 데이터를 소팅(정열)하는것이 필수이고
이게 안되어 있으면 O(log n) 퍼포먼스를 보장 할수 없다
--> 오라클도 새로운 row가 추가 될때 마다 그것의 관련 인덱스를
미리 소팅 해 놓는다

그런데 신입분이 ..저보고 잘못 설명하는것 같다고 .. 오라클의 인덱스는
BST (바이너리서치 트리)이고 노드과 트리 개념이 들어 있어서
먼가를 서치 (where 절에서 인덱스 칼럼 조건) 할때 정렬 STEP 이
필요 없다고 하네요.

그리고 jdk의 binary search와 그것을 실행하기전에 Comparable
인터페이스에서 -1,0,1 의 int compareTo()를 오버라이드 해서
구현하는것은 오라클의 인덱스 원리와 전혀다른 개념이라고 하시는겁니다.

저는 비전공자이고 ..알고리즘 지식은
- 생각하는 프로그래밍이란 책
- 파견지 회사에서 코딩하면서 익힌 현장 경험

이거 두개밖에 없습니다만.. 1996년부터 개발일 했습니다.인덱스 바이너리

저는 위에 책에서 간단한 산수로 설명한 바이너리서치 내용이
자바의 collections 패키지와 딱 맞아 떨어지고
디바이드 & 컹커 방식으로 쪼개는 방식으로 바이너리 서치 방식을
채용하고 있다면 (오라클 인덱스 내부적 구현)
반드시 머지소팅이든 머든 정열이 바이너스 서치 호출전에 필수이고

결국 같은 개념이라고 생각하는데 제가 잘못생각하는건가요?
오라클 인덱스의 BST (binary Search Tree)와
JDK collections 패키지의

public static > void sort(List list)

public static int binarySearch(List> list, T key)

Tree라는 구조체만 빼면 어차피 List가 인터페이스이니까
ArrayList 이든지 LinkedList 이든지 상관이 없이
바이너리 서치전에는 반드시 소트/정열을 해야하는게 맞죠?

BST는 노드가 존재하니 링크드 리스트를 사용하는 케이스라면
이전검색전에 전체 리스트를 정열할 필요가 없고
이게 오라클 인덱스에서 사용하는 기법인가요?

제가 역쉬 비전공자라 자료구조와 알고리즘에 대해서 개념이 부족해서
제 궁금증을 잘 설명 했는지 모르겠습니다 ㅋ

신입분이 오셨는데 가끔 SQL 이 할일을 자바 WAS 단에서
비지니스오브젝트를 구현해서 Comparable 인터페이스 안에서
이 업무만의 order by (내츄널 오더가 아닌 임의로 구현된 정열)
로 -1,0,1 의 int compareTo()를 오버라이드 해서 설명하는것을

어떻게 오라클 order by 역할을 was단에서 대체하는것인지
제 나름대로 for 구문으로 자바스크립단에서 서치 안하고
자바 facade 레벨에서 JDK 바이너리 서치 함수를 이용하는것을
오라클 인덱스를 잘 설명하고 싶은데 제가 워낙 전산기초가 약해서
힘드네요 ㅋㅋ

가끔 이럴때 15년 넘도록 한달도 안쉬고 코딩에 전념해도
너무 전공파트를 공부 안하면 후배님들에 설명도 헤메고
설명하면서 나도 헤메고 .. 거참 답답하네요

이런식으로 디른은행에서 문제 없어서 여기서도 이렇게 하는데
그것을 알고리즘 기반으로 깔끔하게 설명이 안되네요 ㅋ
도와 주세요 ^^

인덱스 바이너리

블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다.

Fenwick Tree를 구현하려면, 어떤 수 X를 이진수로 나타냈을 떄, 마지막 1의 위치를 알아야 합니다.

마지막 1이 나타내는 값을 L[i] 라고 표현하겠습니다. L[3] = 1 , L[10] = 2 , L[12] = 4 이 됩니다.

수 N개를 A[1] ~ A[N] 이라고 했을 때, Tree[i] 는 A[i] 부터 앞으로 L[i] 개의 합이 저장되어 있습니다.

아래 그림은 각각의 i 에 대해서, L[i] 를 나타낸 표입니다. 아래 초록 네모는 i 부터 앞으로 L[i] 개가 나타내는 구간입니다.

L[i] = i & -i 가 됩니다. 그 이유는 아래와 같습니다.

A = [3, 2, 5, 7, 10, 3, 2, 7, 8, 2, 1, 9, 5, 10, 7, 4]인 경우에, 각각의 Tree[i] 가 저장하고 있는 값은 다음과 같게 됩니다.

예를 들어, Tree[12] 에는 12부터 앞으로 L[12] = 4 개의 합은 A[9] + A[10] + A[11] + A[12] 가 저장되어 있습니다. Tree[7] 에는 7부터 앞으로 L[7] = 1 개의 인덱스 바이너리 합인 A[7] 이 저장되어 있습니다.

합 구하기

Tree 를 이용해서 A[1] + . + A[13] 은 어떻게 구할 수 있을까요?

13을 이진수로 나타내면 1101입니다. 따라서, A[1] + . + A[13] = Tree[1101] + Tree[1100] + Tree[1000] 이 됩니다. Tree 의 인덱스는 이진수입니다.

1101 -> 1100 -> 1000 는 마지막 1의 위치를 빼면서 찾을 수 있습니다. 이것을 코드로 작성해보면 다음과 같습니다.

모든 i 에 대해서, A[1] + . + A[i] 를 구하는 과정을 그림으로 나타내면 다음과 같습니다.

어떤 구간의 합 A[i] + . + A[j] 는 A[1] + . + A[j] 에서 A[1] + . + A[i-1] 을 뺀 값과 같습니다. 따라서, sum(j) - sum(i-1) 을 이용해서 구할 수 있습니다.

어떤 수를 변경한 경우에는, 그 수를 담당하고 있는 인덱스 바이너리 인덱스 바이너리 구간을 모두 업데이트해줘야 합니다. 아래와 같이 마지막 1의 값을 더하는 방식으로 구현할 수 있습니다.

바이너리 인덱스 트리

2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조를 의미합니다.

펜윅 트리(Fenwick Tree)라고도 합니다.

세그먼트 트리의 한 종류로 더 빠르고 효율적으로 동작합니다.

0이 아닌 마지막 비트를 찾는 방법은 특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서 (K & -K)를 계산하면 됩니다.

세그먼트 트리 (Segment Tree)

배열에 부분 합을 구할 때 사용하는 개념입니다.

제일 아래 리프 노드로 달린 것들이 실제 우리가 인덱스 바이너리 처음 받아온 데이터들을 의미합니다.

부모 노드 값은 아래 자식 노드 값들의 합입니다.

바이너리 인덱스 트리 원리

바이너리 인덱스 트리를 구성하면 해당 인덱스의 2진수에서 제일 마지막(제일 오른쪽)에 있는 1을 1씩 빼주면 필요한 구간들이 나옵니다.

예를 들어 2에서 7까지의 구간합 [2,7]을 구해보겠습니다.

먼저 7의 2진수 0111에서 처음 구간 [7]과 1을 뺀 0110인 6의 구간 [5,6] 그리고 또 1을 뺀 0100인 4의 구간 [1,4]를 모두 더하면 [1,7]을 구할 수 있습니다.

그리고 2의 2진수 0010의 처음 구간 [1,2]를 빼주면 구간합 [2,7]을 구할 수 있습니다.

• 해당 인덱스 K의 0이 아닌 마지막 비트를 찾기 위해서 비트연산 and를 이용해 K & -K 를 해주면 위치를 찾을 수 있습니다.
• 위의 그림처럼 7과 -7의 and 연산을 해주면 오른쪽 끝만 1이 되고 나머지는 모두 0으로 변합니다.

위의 계산 결과 표를 보면 K가 7일 때, 2진수 표기시 가장 마지막 1의 위치가 1의 자리인 것을 알 수 있습니다. 즉 K & -K를 통해서 해당 인덱스가 가지고 있는 구간 합 범위를 알 수 있습니다.

K의 K & -K값이 1이면 해당 인덱스는 K값 하나만 가지고 있습니다. 2이면 (K-1 + K)의 값을 가지고 있습니다. 4이면 (K-3 + K-2 + K-1 + K)의 값을 가집니다.

• 특정 K번째 인덱스의 수를 변경할 경우에는 그 인덱스 바이너리 뒤의 모든 구간 합을 수정하지 않고 해당 인덱스의 2진수에서 가장 마지막 1에 1씩 더해준 구간들만 변경하면 됩니다.

① 구간 합 구하기

❔ 문제 설명

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다.

만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다.

그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 인덱스 바이너리 합을 구하여 출력하면 된다.

인덱스 바이너리

Binary Indexed Tree( 이하 BIT) 는 알고리즘이라기 보다는 자료구조에 가깝지만, 흔히 기본 자료 구조라고 할 수 있는 스택, 큐와 같은 자료구조보다는 고급의 자료구조이다. 사촌 격인 Segment Tree 도 있으나 조금 더 설명하기가 어렵기 때문에 본 포스팅에서는 Binary 인덱스 바이너리 Indexed Tree 만 소개한다.

BIT의 원래 명칭은 Fenwick Tree 이며, 구현 상 Binary Tree 를 이용하기 때문에 BIT(Binary Indexed Tree) 라고 부른다.

이 이진트리 형태의 자료구조는 효과적으로 부분 요소의 갱신(Update) 와 조회(Select) 를 하기 위하여 만들어진 자료구조로, 많은 변경과 많은 데이터의 조회가 빈번하게 일어날 때 한번에 처리할 수 있는 간단하면서도 유용한 자료구조이다.

특히, 데이터의 일부분이 갱신되었을 때 데이터 전체의 값이 변하는 경우, 가령 데이터 전체의 총합을 구하거나 최댓값을 구하는 일 등을 가장 효과적으로 수행할 수 있는 자료구조이다.

설명을 위해 다음 배열을 준비해보았다.

준비한 배열은 음. 온라인 게임의 유저들의 점수를 나타낸 랭킹 Database라고 해보자. 6명의 유저들이지만 엎치락 뒤치락하고 있는 것을 볼 수 있다.

이 데이터베이스에서 가장 점수가 높은 유저는 맨 앞에 있는 10점을 획득한 유저이고, 최고점은 10점이다. 최고점을 우리는 DB를 모두 뒤져 시간복잡도 O(N) 만에 최댓값을 찾아내었다. 그런데 10분뒤 상황이 바뀌었다.

갑자기 몇몇 유저의 약진에 힘입어 10점을 획득한 유저는 3등이 되었다. 이런.. 당신은 다시 최고점을 구하기 위하여 DB를 모두 뒤져 최댓값 15를 찾아내기에 이른다. 시간복잡도는 O(N)

이 구조는 효과적일까? 전혀 그렇지 않다. 심지어 실시간 게임이라면 이런식으로 관리했다간 100만명의 유저에 대해 매 Tick 마다 100만명을 전부 검사해야 한다. 물론 알고리즘의 적용 대상을 이런 종류의 실시간 서비스를 예시로 드는건 적절하지 않아보이지만, 더 최적화할 수 있는 방안은 분명히 있다.

위의 그림은 BIT 가 적용된 새로운 자료구조를 보여준다. 위에 인덱스 바이너리 보이는 것 처럼 Binary Tree 를 이용한 구조는 추가적인 메모리를 사용하지만, 토너먼트 형태로 최댓값을 구해내고 있다. 또한 보면 알 수 있겠지만 범위별로 최댓값을 구하는 것도 가능하다. 토너먼트를 해당 범위에 대해서만 열면 그만이다.

눈치챌 수 있겠지만 이 자료구조는 토너먼트 형식을 이용해서 비교해야할 대상과만 비교한다. 가령, A가 B보다 크다는게 보장이 되었을 때, C가 B보다 크다면 A와 C는 서로 비교할 필요가 없다. 전부 비교할 필요 없이 두번만에 최댓값 C를 구할 수 있는 것이다.