데지덤

  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. B+ Tree의 개요

가. B+Tree의 필요성

1) 데이터가 순차적으로 처리되어야 할 때는 트리 구조 내에서 노드 사이를 오르내리는데 많은 처리 시간이 필요하게 되는데 이런 경우 B+트리를 사용

- m-차수 트리의 한 종류로 노드의 Balance 를 맞춘 트리로 효율적인 균형 탐색 알고리즘을 제공함

- B 트리의 변형으로 인덱스 세트(index set)와 순차세트(sequence set)로 구성

 

  나. B Tree와 차이점

- 인덱스 세트에 있는 키 값 : 리프 노드에 있는 키 값을 찾아가는 경로만 제공하기 위해서 사용

- 인덱스 세트의 노드와 순차 세트의 노드는 그 내부 구조가 서로 다름

. 인덱스 세트에 있는 노드 : 키 값만 저장, 리프 노드 : 키 값과 포인터가 함께 저장

- 순차 세트의 모든 노드가 순차적으로 서로 연결된 연결 리스트 (순차 접근이 효율적)

  다. B Tree의 특징

- 루트는 0 또는 2에서 m개 사이의 서브트리를 가짐

- 루트와 리프를 제외한 모든 내부 노드는 최소 ⌈m/2⌉개, 최대 m개의 서브트리를 가짐

- 리프가 아닌 노드에 있는 키 값의 수는 그 노드의 서브트리 수보다 하나 적음

- 모든 리프 노드는 같은 레벨이며, 한 노드 안에 있는 키 값들은 오름차순

- 리프 노드는 모두 링크로 연결되어 있다

- 리프 노드의 키 값의 수는 [m/2] 이상이다

 

2.B+tree의 구성

  가. B+ Tree의 구성 및 동작

- Index Set : 키, 포인터만 존재

. Index Set에 있는 Node는 Leaf를 찾아갈 수 있는 Key 값과 Pointer 값만 가지고 있음

- Leaf Node관련 키값은 오름차순으로 정렬되어 있으며 삽입으로 인한 분기시 Sequence Set에 연결되면서 순차성 유지: 성능저하해결

- 삭제는 Leaf에서만 수행, 키 값은 Index Set에 유지하되 탐색 시에는 사용되지 않고 split값으로만 사용

 

  나. B+tree의 data 구조/특징

1) 인덱스 세트 : 실제적인 키 값(Leaf node)를 찾아갈 수 있는 경로제공이 목적

- 인덱스 세트에 있는 노드는 키 값만 존재

- 각 노드는 키 값과 Sub-tree에 대한 포인터를 포함

- 인덱스 세트의 키 값은 Leaf node에 있는 키 갑을 찾아 갈 수 있는 직접 경로를 제공

 

        2) 순차세트(Sequence Set)

- Leaf Node값은 오름차순으로 정렬되어 있으며, 삽입으로 인한 분기 시 Sequence Set에 연결되면서, 순차성 유지 : 성능 저하 해결

- 각각의 노드는 순차접근을 할 수 있도록 링크되어 순차접근이 용이

 

  다. B+tree의 연산

1) 삽입

  - B-트리와 유사하며, 리프의 오버플로우가 발생하면, 두 개의 노드로 분할하고 키 값들을 절반씩 분배해서 저장하며, 분할된 왼쪽노드에서 제일 큰 키 값을 부모 인덱스 노드로 저장

   -> B 트리와의 차이점은 중간 키 값이 부모 인덱스 노드 뿐만 아니라 새로 분할된 노드에도 저장됨

2) 삭제

  - 리프 노드에서만 삭제

    ㆍ인덱스 노드에서는 분리자(separator)로 유지 (∵ 다른 키 값을 탐색하는데 분리 키 값으로만 사용)

    <<키 값 43을 삭제한 이후의 트리>>

   - 언더플로우로 인해 재분배가 일어나는 경우 : 인덱스 키 값 조정 (110 -> 90)

    <<키 값 125의 삭제>>

- 언더플로우로 인해 합병이 일어나는 경우 : 인덱스 키 값 삭제 (43)

<<키 값 55의 삭제>>

 

 

3. 기타 Tree(B*Tree, Red-Black Tree, Trie)

  가. B* tree

-  B-tree의 문제점(보조연산 필요)를 보완하기 위해서 B-tree를 약간 변형한 트리(보조연산 회수를 줄임)

-  B-tree에 비해 공간활용도를 높일 수 있음(B-tree는 최소 1/2면 분열할 수 있지만, B* tree는 최소 2/3가 되어야 분열함)

- 노드의 분열을 줄여서 보조연산 회수를 감소시킴. 노드가 꽉 차면 분열하지 않고 형제 노드로 재배치(인접 노드 찰 때까지 지연 가능)

 

B*-Tree (Knuth 제안)

B-Tree의 단점

분열, 재분배, 합병 연산이 빈번 -> node 수 증가

각 node는 절반 정도가 Key값으로 채워짐

 

  B*-Tree의 기본 Idea

Overflow 발생시 Split 대신 형제 node로 재분배

      형제 node가 모두 Overflow이면 두 node를 세 node로 분할

=> 각 node는 2/3 정도가 채워짐

 

나. Red-Black Tree

- 각각의 노드가 레드 나 블랙 인 색상 속성을 가지고 있는 이진 탐색 트리

- 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장 (worst-case guarantees)

- 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배 보다 항상 작다

 

  다. Trie

- 노드가 모두 포인터로 구성되며 해당 포인터 위치가 값을 의미

- 자료 탐색시 B+-tree와 같이 leaf node까지 가야만 key 값을 획득

- 찾는 key 값이 없을 경우 어느 level에서든지 끝낼 수 있어 key 값이 없는 경우의 탐색 효율 우수

댓글