데지덤

  1. 데이터관련 직무와 자격
    1. 데이터베이스 직무

    2. 데이터베이스 자격

  2. 데이터관련 학습방법
    1. 데이터베이스 개론 학습

    2. DBMS 학습

    3. 읽어볼만한 DB책

  3. 최신동향과 유명한 Things
    1. DB최신동향

    2. 데이터로 유명한 Things

  4. 데이터베이스 개념
    1. 데이터베이스 개념

    2. DBMS

    3. 데이터베이스 개발과운영

  5. 데이터베이스 설계(1/2)
    1. 데이터표준

    2. 데이터모델링

    3. 데이터모델 디자인패턴

  6. 데이터베이스 설계(2/2)
    1. 프로세스및상관모델링

    2. 정규화

    3. 반(역)정규화

    4. DB물리설계

  7. 인덱싱과 DB프로그래밍
    1. 인덱스와 해싱

    2. 관계연산

    3. DB언어

    4. SQL

    5. 데이터베이스 미들웨어

  8. 데이터베이스 운영
    1. 트랜잭션

    2. 병렬처리

    3. 데이터베이스 복구

    4. 데이터베이스 성능

    5. 병행제어(동시성제어)

  9. 분석계 및 빅데이터기술
    1. 데이터웨어하우스

    2. 데이터마이닝

    3. 빅데이터기술

  10. 데이터거버넌스
    1. 데이터거버넌스

    2. 데이터베이스 감리/진단

  11. 데이터베이스 종류와 보안
    1. 데이터베이스 종류

    2. 데이터베이스 보안

  12. DBMS
    1. 오라클

    2. SQL Server

    3. DB2

    4. Sybase

    5. Altibase

B-Tree

개념
데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조로. 트리의 루트로부터 하나의 노드에 이르는 모든 경로가 일정한 깊이를 유지하며 데이터의 접근시간이 동일함

1. Balanced Tree를 통한 균등한 응답속도 보장을 위한 탐색 트리, B-Tree 개요

  가. B-Tree의 정의

    - 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조

     * B 는 Balanced의 의미이며, leaf node가 한쪽 방향으로 쏠리는(skewed) 현상이 적음

 

  나. B-Tree의 특징

    - 각 노드는 1/2 이상 채워져야하며, 모든 leaf node는 같은 level에 있음

    - 탐색, 추가, 삭제는 root node로부터 시작함

    - 노드 내 값은 오름차순 유지

    - 공백이거나 높이가 1이상인 m-원 탐색 트리(m-way search tree)

    - 루트와 리프(leaf)를 제외한 내부 노드는 최소 [m/2], 최대 m개의 서브트리를 가지며, 적어도 [m/2]-1개의 키 값을 가짐 -> 적어도 반 이상이 키 값으로 채워져 있어야 한다

    - 루트는 그 자체가 리프가 아닌 이상 적어도 두 개의 서브트리를 가짐

    - 모든 리프는 같은 레벨에 있음 (균형 트리)

 

2. B-Tree의 구조와 장점 및 단점

  가. B-Tree의 구조

 

   - In Order Tree Traversal 순서: 5, 10, 20, 25, 30, 40, 50, 100

 

  나. B-Tree의 장점과 단점

장점

1) 삽입, 삭제 후에도 균형 트리 유지

2) 효율적인 알고리즘 제공

3) 저장 장치의 효율성

4) 균등한 탐색 속도 보장 가능

단점

1)노드의 삽입과 삭제 시 트리의 균형을 유지하기 위해 복잡한 연산(재분배, 합병)이 필요

2) 순차탐색 시에 inorder(중위) 순회로 비효율적

à B+ Tree 구조에서 leaf node간의 linked list로 순차 탐색 효율 향상됨

 

3. B-Tree와 B+tree의 비교 및 활용

   가. B-Tree와 B+tree의 비교

구분

B-tree

B+tree

접근성

- 순차 접근이 어려움

- 탐색 중 원하는 키 값의 레코드 위치를 파악해야 함

- 순차 접근이 용이함

- 레코드의 위치는 leaf node에서만 파악됨

중복성

- 탐색 키의 중복성을 제거함

- Index Set와 Sequence Set에 중복성 존재

복잡성

- non-leaf node 크기가 더 크며 tree에 대한 저장공간 관리가 복잡함

- 모든 node 크기가 같으며 삭제될 node가 항상 lead node에 존재함

 

  나. B-tree의 활용

    - DBMS의 인덱스 자료구조로 활용 됨(B+tree 및 B*tree로 발전 적용)

    - 검색엔진, 패턴 매칭 등 빠르면서도 성능이 일정하게 유지되는 탐색이 요구되는 분야에 활용됨

 

4. B-Tree 연산

  가. 삽입

- 리프노드에 빈 공간이 있는 경우 : 단순히 빈 공간에 삽입하면 됨

- 오버플로 발생 시

1) 두 노드로 분열(split)

2) ⎡m/2 ⎤ 째의 키 값 -> 부모노드

3) 나머지는 반씩 나눔 (왼쪽, 오른쪽 서브트리)

 

 

 

 

   - 새로운 값 "59"가 추가된 경로를 간략히 설명

 

나. 삭제

  - 리프노드에서 삭제

  - 삭제키가 리프가 아닌 노드에 존재

. 후행키 값과 자리교환(후행키-항상 리프에)

. 리프노드에서 삭제

- 언더플로 : 키수 < ⎡m/2⎤ -1

. 재분배 (redistribution) : 최소키 수 이상을 포함한 형제노드에서 이동

(형제노드의 키 → 부모노드 → 언더플로 노드)

. 합병 (merge) : 재분배 불가능시 이용 (형제노드 + 부모노드의 키 + 언더플로 노드)

 

댓글