본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

범위 검색을 위한 $CST^+$ 트리 인덱스 구조
A $CST^+$ Tree Index Structure for Range Search

이재원   (서울대학교 컴퓨터공학부UU0000691  ); 강대희   (서울대학교 컴퓨터공학부UU0000691  ); 이상구   (서울대학교 컴퓨터공학부UU0000691  );
  • 초록

    최신 컴퓨터 시스템의 새로운 병목 현상이 메모리 접근에서 발생하고 있다. 메모리의 접근 속도를 줄이기 위해 캐시 메모리가 도입되었지만, 캐시 메모리는 원하는 데이타가 캐시에 옮겨져 있어야 메모리 접근 속도를 줄일 수 있다. 이를 해결하기 위해 기존의 T 트리를 개선한 CST 트리가 제안되었다. 하지만, CST 트리는 범위 검색 시, 불필요한 노드를 검색해야 한다는 단점이 있다. 본 논문은 캐시 효율적인 CST 트리의 장점을 가지며, 범위 검색이 가능하도록 하기 위해 연결 리스트로 각 노드를 연결한 $CST^+$ 트리를 제안하였으며, CST 및 $CSB^+$ 에 비해 $4{\sim}10$ 배의 성능 향상을 보였다. 또한, 메인 메모리 데이타베이스 시스템 장애 시, 빠른 데이타베이스 복구를 위해 인덱스의 빠른 재 구축은 전체 데이타 복구 성능에 있어 매우 중요한 부분이다. 이를 위해 본 논문은 병렬 삽입 기법을 제안하였다. 병렬 삽입은 노드 분할 오버헤드가 없으며, 데이타 복구 단계와 인덱스 구축 단계를 병렬로 수행할 수 있는 장점이 있다. 병렬 삽입은 순차 삽입 및 일괄 삽입에 비해 $2{\sim}11$ 배의 성능 향상을 보였다.


    Recently, main memory access is a performance bottleneck for many computer applications. Cache memory is introduced in order to reduce memory access latency. However, it is possible for cache memory to reduce memory access latency, when desired data are located on cache. EST tree is proposed to solve this problem by improving T tree. However, when doing a range search, EST tree has to search unnecessary nodes. Therefore, this paper proposes $CST^+$ tree which has the merit of CST tree and is possible to do a range search by linking data nodes with linked lists. By experiments, we show that $CST^+$ is $4{\sim}10$ times as fast as CST and $CSB^+$ . In addition, rebuilding an index Is an essential step for the database recovery from system failure. In this paper, we propose a fast tree index rebuilding algorithm called MaxPL. MaxPL has no node-split overhead and employs a parallelism for reading the data records and inserting the keys into the index. We show that MaxPL is $2{\sim}11$ times as fast as sequential insert and batch insert.


  • 주제어

    메인 메모리 .   인덱스 구조 .   캐시 .   $CST^+$ 트리 .   범위 검색.  

  • 참고문헌 (9)

    1. 이익훈, 김현철, 허재녕, 이상구, 심준호, 장준호, "캐시를 고려한 T 트리 인덱스 구조", 한국정보과학회 논문지, 제32권 제1호, pages 12-23, 2005     
    2. 이재원, 이익훈, 이상구, "최대 키 값을 이용한 CST-트리 인덱스의 빠른 재구축", 한국정보과학회 2005:데이타베이스, pages 85-87, 2005 
    3. J. Rao and K. A. Ross, "Making B+ Trees Cache Conscious in Main Memory," Proceedings of ACM SIGMOD 2000 Conference, pages 475-486, 2000 
    4. K. R. Choi, K. C. Kim, "T*-Tree: A Main Memory Database Index Structure for Real Time Applications," Proceedings of the 3rd International Workshop on RTCSA, pages 81-89, 1996 
    5. P. Boncz, S. Manegold, and M. Kersten, "Database Architecture Optimized for the new Bottleneck: Memory Access," Proceedings of the 19th VLDB Conference, pages 54-65, 1999 
    6. Ig-hoon Lee, Junho Shim, Sang-goo Lee, "Fast Rebuilding B+ Trees for Index Recovery," IEICE Transactions on Information and Systems, vol. E89-D(7), pages 223-233, 2006 
    7. T. J. Lehman and M. J. Carey, "A Study of Index Structures for Main Memory Database Management Systems," In Proceedings of the 12th VLDB Conference, pages 294-303, 1986 
    8. SangWook Kim, HeeSun Won, "Batch Construction of $B^+$-Trees," Proceedings of ACM Symposium on Applied Computing 2001, pages 231-235, 2001 
    9. 강대희, 이재원, 이상구, "CST-트리의 효과적인 범위 검색", 한국정보과학회 2006: 데이타베이스, pages 67-69, 2006 

 저자의 다른 논문

  • 이재원 (3)

    1. 2008 "SRM 솔루션을 통한 국가 공공조달 시스템 혁신 방안" 정보과학회논문지. Journal of KIISE. 컴퓨팅의 실제 및 레터 14 (9): 823~834    
  • 강대희 (38)

  • 이상구 (41)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기