대용량 검색을 위한 TRIE 업그레이드

대용량 데이터를 검색할 일이 생겼다.

사용목적은 개인적 용도이고 prefix search가 가능해야 한다.

 

b+tree 또는 trie로 구현을 해야할것 같은데

b+tree라면 굳이 구현할 필요 없이 리눅스에 있는 버클리 db를 쓰면 된다.

그런데 문제는 데이터가 커지면 버클리 db가 상당히 느려진다는 것이다.( 밸런스 잡는데도 시간이 많이 걸리기도 하지만 page 단위로 데이터를 관리하는데 page 분할이 많이 발생해서 그렇기도 하고 암튼 다른것도 마찬가지겠지만 버클리 db는 더욱 느려진다 )

 

테스트 삼아 버클리 db로 빌드하니 빌드된 파일이 2G 정도 나온다.

엔트리가 3천1백만개 문자열(680M)이니 그정도 나올수도 있을것 같다.

 

prefix search도 해야되서 trie로 될까 싶어 가지고 있는 trie로 테스트를 해보니

어림없다... 빌드하다 바로 죽는다...

 

일단 노드를 최소화 해야 한다. 노드 분할을 꼭 필요한 상황에서만 해야한다. 그렇지 않으면 노드가 너무 많이 발생해서 트리를 만들다가 맛이 간다.

 

트리구조를 가져갈때 필수적인 traverse를 recursive하게 구현할수 없다. 노드수가 많고 depth 또한 깊으니 program stack을 넘어가 버린다.

 

트리를 만들어 놓고 이걸 루프로 순회할려고 하니 이것 또한 만만치 않다. 노드에 변수하나를 추가하는게 녹녹치 않기 때문에 ...

변수가 포인터라면 더 많이 생각을 해야 한다. 포인터 변수는 빼도 박도 못하고 노드당 4byte를 사용한다.

일단 엔트리가 3천만개이니 엔트리당 2개의 노드만 생성된다고 해도 노드수가 6천만이다

6천만 노드에 4바이트씩 추가된다면

60,000,000 * 4 byte = 240,000,000 = 약 240M 정도 되는것 같다. 무시못할 수치다.

 

 

이런 저런 우여 곡절 끝에 3천만개는 빌드에 성공했다. 그런데 3천 1백만개는 빌드할수 없었다.

1백만개를 버릴수도 없고 ..........

 

마지막 튜닝은 padding 비트까지 줄이는 방법이었다. word alignment문제로 속도가 다소 느려질수도 있었지만 데이터 빌드가 먼저라서 속도 감소를 감내하고 테스트를 했더니 3천 1백만개 모두 빌드하는데 성공했다....

 

 

입력 파일 크기 : 680M

출력 파일 크기 :

키 파일 : 605M 

값 파일 : 107M 

노드수 : 약 4천 3백만

빌드시간 : 약 3분 20초

 

키와 값을 합치면 712M 정도인데 원보 파일 680M에 비하면 원본 파일과 인덱싱 후의 파일 크기가 거의 비슷하다.. 트라이구조의 특징이 보인다.