기술보고서 "버클리DB DB_BTree와 DB_HASH의 적재성능 비교"

김진숙 기술보고서 2003-04-15 (2007년 6월 22일 재수정)

버클리DB DB_BTree와 DB_HASH의 적재성능 비교

Embedded Storage Engine인 Berkeley DB 는 KEY-DATA 쌍을 저장하기 위한 구조로써 DB_BTREE (B-⁺Tree)와 DB_HASH를 지원한다. 두가지가 모드가 저장 성능에서 어떠한 차이가 있는 지 알아보기 위해 자그마한 문서를 저장하는 실험을 해보았다. 실험: Pentium Xeon 2.4GHz Dual CPU, 메모리 4GB, Ultra160 SCSI HDD를 장착한 리눅스 장비에서 수행하였다. (그렇게 쓸모있는 실험은 아니었던 것 같다.)

그림 1. 적재시간 비교

그림 1은 건수에 따른 적재시간을 도식화하였다. 100만건까지는 DB_BTREE가 조금 빠르지만 110만건이 되면 거의 같아진다. 추이로 보아서는 DB_BTREE의 경우 건수가 많아질수록 약간은 지수적인 특성을 가지면서 적재시간이 늘어나는 것 같다. HASH의 경우 키의 숫자가 늘어나면 HASH 버킷(bucket)의 수를 증가시키는 간단한 작업만 수행해도 되기 때문에 건수와 적재시간은 거의 선형으로 비례하는 것으로 추정된다. 그러나 B+tree의 경우에는 단말노드의 정렬 때문에 키의 수가 늘어날 수록 작업 오버헤드가 증가하는 것 같다. 그렇다고 하더라도 건수가 매우 많이 늘어난 경우의 현상이므로 일반적인 데이터저장구조로 사용하기에는 B+Tree가 조금 더 낳은 성능을 보인다고 할 수 있겠다.

그림 2는 그림 1의 실험결과로 생성되는 테이블의 크기를 보여주고 있다. DB_BTREE와 DB_HASH가 거의 같은 크기를 보여주지만 앞서 설명한 바와 같이 B+tree의 오버헤드 때문인지 건수가 100만 건을 넘어가면 DB_BTREE의 저장공간 오버헤드가 더 큰 것을 알 수 있다.

그림 2. 테이블 크기 비교

실험적인 결과로는 단순한 저장구조로서는 중소 용량에서는 DB_BTREE가 낳고 대용량으로 갈 수록 DB_HASH가 더 큰 장점을 가질 수 있다고 결론을 지을 수 있겠다. 단일 데이터의 접근에 있어서는 DB_HASH가 DB_BTREE보다는 빠를 것으로 예상되기 때문에, 포인트식으로 데이터를 접근하는 작업이 많은 시스템에서는 DB_HASH가 큰 장점을 가질 수 있을 것이다.

다만 HASH 구조에서는 단말 노드가 정렬이 되어 있지 않아서 정보검색엔진에 사용할 경우에는 색인어 접근이 어려운 단점이 있다. 따라서 우절단검색같은 기능을 제공하고자 할 경우에는 색인정보를 B+Tree에 저장하는 것이 좋다. (KRISTAL에서는 역파일 구조로서 B+Tree를 쓴다. 일반적으로 다른 엔진들도 B+tree를 사용하는 것으로 보아 색인정보를 저장하는 데는 별 다른 현실적인 대안은 없는 것 같다.)