[DB] Index, B-Tree , B+Tree

Index

데이터베이스에서 인덱스란 테이블에 대한 검색성능 속도를 높여주는 자료 구조입니다.

특정컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리공간에 데이터의 물리적 주소와 함께 저장 됩니다.

 

인덱스의 단점으로는 항상 최신의 데이터를 정렬된 상태로 유지해야 빠르게 값을 탐색할수있기에

INSERT, DELETE, UPDATE 구문이 실행 된다면 계속해서 정렬을 해줘야 하고 이로인한 부하가 발생합니다.

때문에 인덱스에서는 이런 부하를 최소화 하기위해 데이터 삭제라는 개념에서 인덱스를 사용하지않음이라는 작업을 합니다.

 

INSERT =  새로운 데이터에 대해 인덱스를 추가합니다.

UPDATE = 기존 인덱스를 사용하지않음 처리 후, 업데이트 된 데이터에 인덱스를 추가함.

DELETE =  삭제되는 데이터의 인덱스를 사용하지않음 처리 작업

 

이중많이 사용 되는 구조로는 B-Tree 와 B+Tree 가 있습니다.

B-Tree

B-Tree는 탐색성능을 높이기 위해 높이를 균형있게 유지하는 Balanced Tree의 일종입니다.

 

만약 균형이 유지되지않은 비균형 트리일 경우 최악의 경우 O(N)의 시간복잡도를 가지는 구조가 될 수 있지만

항상 균형을 유지하는 Balanced Tree의 경우 O(logN)의 시간복잡도를 가지게 됩니다.

 

B+Tree

B+Tree는 B-Tree의 확장된 구조입니다

B-Tree와 다르게 leaf 노드에만 key,data가 모두 담겨있고 , 브랜치 노드에는 data가 담기지않고 key만 담겨 있습니다.

또 하나의 특징으로는 leaf 노드 끼리 LinkedList로 연결 되어있습니다 .

 

leaf노드를 제외하고 data를 담지않는 특징 때문에 더 많은 메모리를 확보하고,하나의 노드에 더 많은 key를 담을 수 있게 되어

전체적인 트리의 높이가 낮아지게 됩니다.

leaf 노드 끼리 LinkedList로 연결 되어있는 특징으로 , Fullscan시에 B-tree와 다르게 leaf노드에서 선형탐색이 이루어져서

큰 이점을 가지게 됩니다.

 

구분	B-tree	B+tree
데이터 저장	리프 노드, 브랜치 노드 모두 데이터 저장 가능	오직 리프 노드에만 데이터 저장 가능
트리의 높이	Balanced Tree이기에 낮음	B-Tree에 비해 낮음
풀 스캔 시, 검색 속도	모든 노드 탐색	리프 노드에서 선형 탐색
키 중복	없음	있음(리프 노드에 모든 데이터가 있기 때문)
검색	모든 노드에 데이터가 존재하기 때문에 , 자주 액세스가 되는 노드의 경우 루트노드에 액세스 하려는 노드가 가까울 경우 더 빠르게 액세스가 가능합니다	리프 노드까지 가야 데이터 존재
링크드 리스트	없음	리프 노드끼리 링크드 리스트로 연결

 

 

참고:

https://zorba91.tistory.com/293

https://stackoverflow.com/questions/870218/what-are-the-differences-between-b-trees-and-b-trees