B-Tree

B(Balanced) 트리 : 1/2, 순차접근

 

[개념] balanced tree, 균형된 트리로써 효율적인 알고리즘 제공

[조건] 각 노드는 1/2이상 채워져야함, 처음부터 분기

트리 레벨이 균형유지, 밸런스의 skew를 막기위해 노드 split발생

[구성] Index key value + Rowid

[장/단점] 트리 레벨이 균형을 유지하므로 균등한 응답속도

순차접근시 inorder 순회에 따라 성능저하 발생 -> B+트리로 해결

B+트리와 비교: B트리는 균형(balance)위해 각 노드들간 데이터 이동 양,회수가 많아지게 된다

 

B+트리 : 1/2, index set, sequence set, linked list

[개념] 삽입시의 빈번한 split현상을 줄인 트리

[조건] root, leaf 이외의 노드는 1/2이상 채워져야함

Sequence set이 Linked list로 연결되었음을 강조

 

B*트리 : 2/3, 보조연산문제 개선

공간활용도 66%

[개념]

B트리의 보조연산문제를 개선하여 공간활용도를 66%로 상승시킨 자료구조

 

인덱스는 결국 지정한 컬럼들을 기준으로 메모리 영역에 일종의 목차를 생성하는 것입니다.

insert, update, delete (Command)의 성능을 희생하고 대신 select (Query)의 성능을 향상시킵니다.

여기서 주의하실 것은 update, delete 행위가 느린것이지, update, delete를 하기 위해 해당 데이터를 조회하는것은 인덱스가 있으면 빠르게 조회가 됩니다.

인덱스가 없는 컬럼을 조건으로 update, delete를 하게 되면 굉장히 느려 많은 양의 데이터를 삭제 해야하는 상황에선 인덱스로 지정된 컬럼을 기준으로 진행하는것을 추천드립니다.

 

B-Tree 인덱스 구조

• 인덱스 탐색은 Root -> Branch -> Leaf -> 디스크 저장소 순으로 진행됩니다.

• 예를 들어 Branch (페이지번호 2) 는 dept_no가 d001이면서 emp_no가 10017 ~ 10024까지인 Leaf의 부모로 있습니다.

• 즉, dept_no=d001 and emp_no=10018로 조회하면 페이지 번호 4인 Leaf를 찾아 데이터파일의 주소를 불러와 반환하는 과정을 하게 됩니다.

• 인덱스의 두번째 컬럼은 첫 번째 컬럼에 의존해서 정렬되어 있습니다.

• 즉, 두번째 컬럼의 정렬은 첫번째 컬럼이 똑같은 열에서만 의미가 있습니다.

• 만약 3번째, 4번째 인덱스 컬럼도 있다면 두번째 컬럼과 마찬가지로 3번째 컬럼은 2번째 컬럼에 의존하고, 4번째 컬럼은 3번째 컬럼에 의존하는 관계가 됩니다.

• 디스크에서 읽는 것은 메모리에서 읽는것보다 성능이 훨씬 떨어집니다.

• 결국 인덱스 성능을 향상시킨다는 것은 디스크 저장소에 얼마나 덜 접근하게 만드느냐, 인덱스 Root에서 Leaf까지 오고가는 횟수를 얼마나 줄이느냐에 달려있습니다.

• 인덱스의 갯수는 3~4개 정도가 적당합니다.

• 너무 많은 인덱스는 새로운 Row를 등록할때마다 인덱스를 추가해야하고, 수정/삭제시마다 인덱스 수정이 필요하여 성능상 이슈가 있습니다.

• 인덱스 역시 공간을 차지합니다. 많은 인덱스들은 그만큼 많은 공간을 차지합니다.

• 특히 많은 인덱스들로 인해 옵티마이저가 잘못된 인덱스를 선택할 확률이 높습니다.

B 트리는 이석호 교수님의 데이터베이스론에 있는 내용을 토대로 간략히 정리해 보았습니다.

 

 

m-원 균형탐색트리의 규칙을 적어보면..아래와 같습니다.

(아래 4가지 규칙을 베이스로 삽입, 삭제 알고리즘을 풀어나가야 그나마 덜 헷갈릴거 같습니다)

 

1) B-트리는 공백이거나 높이가 1이상인 m-원 탐색트리 이다

2) 루트와 리프를 제외한 내부 노드는 최소 [m/2], 최대 m개의 서브 트리를 갖는다

   따라서 적어도 [m/2]-1개의 키 값을 갖는다

3) 루트는 그 자체가 리프가 아닌 이상 적어도 두개의 서브트리를 갖는다

4) 모든 리프는 같은 레벨에 있다

 

삽입시 overflow가 발생할 경우 분할(split)이 발생

 

 

 

삭제가 더 복잡한데요

- 삭제 결과로 노드가 유지해야할 최소 키 값의 수 [m/2]-1, 보다 작으면 underflow 발생

- 이럴경우 재분배와, 합병을 이용 최소키 값의 수 유지

 

1) 재분배(redistribution)

  - 해당 노드의 오른쪽이나 왼쪽 형제 노드에 최소 키 값수보다 많은 키 값들이 있는 노드 선택, 한 개 키 값을 차출하여 이동

  - (자연히 부모 노드 관여) 부모 노드에 있는키 를 해당 노드로 이동

  - 부모 노드에 있는 키 값 자리에 차출된 형제 노드의 키 값 이동

  - 재분배는 트리 구조를 변경시키지 않음

 

2) 합병(merge)

  - 재 분배가 불가능할때 적용, 삽입에서 사용한 분할과정의 정반대

  - 해당노드 오른쪽(또는 왼쪽) 형제 노드에 있는 키 값들과 이 두 노드를 분리시키는 부모 노드의 키 값을 모두 모으는 작업

  - 이 결과로 공백이 된 노드는 제거

  - 합병이 수행되는 트리 구조가 변경됨