루씬 파일 시스템 두번째 강좌에서 증분색인(incremental indexing)에 대해서 약간이나마 설명을 했지만 뭔가 다른 설명할 거리가 필요함을 절절하게 느낀 나머지 “증분색인”에 대해서 다시 이야기 해보고자 한다.

루씬은 증분색인을 지원을 함으로서 색인에 문서를 추가했을 경우에 문서 전체를 재색인 할 필요가 없다. 따라서 문서가 추가된 다음에 즉시 검색이 가능하다는 이야기 이다. 그래서 색인에 문서가 추가될 때마다 색인이 있는 디렉토리를 잘 관찰해 보면 색인 파일이 시시각각으로 들쭉 날쭉 하는 모습을 쉽게 볼 수 있을 것이다.

이런 증분색인 알고리즘에 대해서 설명하고자 한다.

*incremental algorithm:

1) maintain a stack of segment indices
2) create index for each incoming document
3) push new indexes onto the stack
4)let b=3 be the merge factor; M=∞
5)for (size = 1; size < M; size *= b) {
  if (there are b indexes with size docs on top of the stack) {
  pop them off the stack;
  merge them into a single index;
  push the merged index onto the stack;
} else {
  break;
}
}

위의 알고리즘은 더그 커팅이 pisa 대학에서 강의한 강의자료에서 가져온 Sudo 코드이다.
그렇지만 이 알고리즘을 이해하기가 쉽지가 않은게 사실이다.

여기서 중요한것은 이 작업이 문서가 추가될 때마다 수행이 된다는 것이다. 이걸 루씬 소스코드에서는 maybeMergeSegments 와 mergeSegments메서드에서 구현하고 있다.
mergeSegments메서드에서는 세그먼트 스택에서 세그먼트들을 꺼네어 병합(merge)하고 다시 스택에 넣는 작업을 하고 있고, 나머지 부분은 maybeMergeSegments메서드에서 수행을 하고 있다.

특히나 5)번 항목에서 if문이 전혀 이해가 갈 수가 없다.ㅋㅋ

if (there are b indexes with size docs on top of the stack)

이부분 말이다. ㅡㅡ;

if문의 의미는 과연 merge할 세그먼트(코드에서는 index라고 했다.)를 몇개나 뽑아올것인가 하는것이다. 이건 전에 강좌에서 이야기 했던 mergefactor와 관계가 있다. 대략적인 이야기는 그곳의 설명을 보면 되겠다.(코드에서는 b가 mergefactor가 되겠다.)

예를 들어 설명해보자면 코드에서 b=3이라고 하고 현재 stak에는 “(3,3,1,1) <-pop되는곳” 이라는 스퀀스로 세그먼트가 저장되어 있다고 해보자. 여기서 숫자는 문서 갯수이다. 여기서 1개의 문서가 추가되서 증분색인 알고리즘이 다시 구동이 된다면 (3,3,1,1,1)이 된다.
여기서 for문의 첫번째 루프는 아무일도 하지 않고 두번째 루프로 넘어가게된다.

첫번째 루프는 그냥 1개의 세그먼트(1)을 뽑아서 그냥 인덱스를 만들고 집어 넣는다.

두번째 루프는 3개의 세그먼트(b=3)이면서 문서 갯수(size)가 3인만큼의 스택포인터에서 문서를 뽑아 merge작업을 하는것이다. 그래서 (3,3,3)의 문서집합이 된다.

마지막 세번째 루프에서 문서 갯수(size)가 9가 되고 b=3(세그먼트 갯수)이 되는 스택포인터인 스택 밑 바닥을 가르키면서 merge를 시켜 최종적으로는 (9)가 되는 것이다.

네번째 루프는 수행이 될 수 없다. 왜냐면 b개의 세그먼트가 존재하지도 않고 27개의 문서가 존재할 수 없기 때문이다.

갠적으로는 첫번째 루프에서 별다른 일을 하지 않기 때문에 size의 초기값을 b로 주는게 좋을거 같다는 생각이 든다.

이 작업을 11개의 문서로 수행한 예제 그림이 아래와 같다.

여기서 알수 있는것들은 아래와 같다.

1. 스택은 4개의 세그먼트를 가지고 있다.
2. 5번의 merge작업이 이루어졌다.

그림이 더 이해하기 편하긴 하다. 하지만 실제 코드가 어떻게 구현되어 있는지 보고자 한다면 위에서 소개한 메서드 두개를 확인해보길 바란다.

Lucene Incremental Algorithm by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.