검색을 위한 자료구조 중에 잠재력이 가장 큰 것은 역시 트리이다. 그 중 이번 포스팅에서는 B-tree에 대해 알아볼 것이다. B-tree는 주로 데이터베이스에서 인덱스를 저장할 때, 많이 사용된다. 이번 포스팅을 찾은 사람 중에 인덱스 관련 글을 보던 중, B-tree에 대해 궁금해져 찾아온 사람도 있을 것이다. 그럼 B-tree에 대해 알아보자.


B-tree의 정의

- 모든 노드는 최대 m개의 자식들을 가진다.

- 루트노드와 리프노드가 아닌 모든노드는 최소 m/2개의 자식을 가진다.

- 루트노드는 최소 2개 이상의 자식을 가진다.

- k개의 자식을 가진 리프노드가 아닌 노드는 k-1개의 키를 가진다.

- 모든 리프노드들은 같은 높이에 있어야 한다.

- 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다.


B-tree의 장점

- 노드의 삽입/삭제 후에도 균형 트리 유지로 균등한 응답 속도를 보장 

- 시간 복잡도 : O(logN)


B-tree의 단점

- 삽입/삭제 시 트리의 균형을 유지하기 위해 복잡한 연산 수행이 필요






알고리즘

검색

- 이진 탐색 트리와 비슷하게 루트노드부터 재귀 호출을 활용하여 탐색을 한다.


삽입

- 해당 원소가 들어가야하는 리프노드를 찾는다.

- 노드에 빈 자리가 있다면 새로운 원소를 삽입한다.

- 노드에 빈자리가 없다면 해당 노드를 2개로 분할한다. 

- 기존 노드의 원소와 새로운 원소 중에 중간 값을 분할된 부모 노드의 값으로 한다.

- 중간 값보다 낮은 값은 왼쪽 노드에 넣고, 큰값은 오른쪽 노드에 넣는다.

- 중간 값을 부모 노드로 넣을 때, 부모 노드에 자리가 없으면 부모 노드도 위의 규칙에 의거하여 분할한다.






삭제 (리프노드)

- 삭제하려는 값을 검색

- 리프노드의 값이면 삭제

- 재배열이 필요한 경우, 재배열 실행


삭제 (중간노드)

- 내부 노드의 값은 하위 노드의 구분 값으로 사용되기 때문에 대체할 수 있는 값이 필요

- 삭제될 값의 자리는 왼쪽 노드의 최대값 혹은 오른쪽 노드의 최소값으로 대체

- 대체된 원소가 원래 있던 노드의 원소가 필요한 만큼 존재하지 않을 경우, 리프노드부터 재배열 실행





참고 : http://arisu1000.tistory.com/27715

자료구조 : 데이터들의 관계를 구조화한 것


자료구조의 분류

선형 자료구조 : 리스트, 스택, 큐

비선형 자료구조 : 트리, 그래프




●배열(Array)

-타입이 동일한 데이터들의 집합

-연속된 공간의 메모리를 할당

-인덱스를 통하여 자료의 순서와 위치를 표시

-인덱스를 이용하여 직접적으로 자료에 접근 가능




●리스트(List)

-특정원소의 탐색

-머리(Head)부터 꼬리(Tail)까지 순차탐색

-i번째 원소의 삽입, 삭제


배열리스트(Array List)

탐색 : 머리(Head)부터 순차탐색 가능, 인덱스를 이용한 직접 접근 가능


삽입 : 끝에 삽입하면 해당 메모리 주소에 삽입, 중간에 삽입하면 이후의 모든 데이터를 뒤로 밀고 삽입


삭제 : 끝에 있는 자료는 바로 삭제, 중간에 있는 데이터는 삭제 후에 이후의 데이터를 모두 당긴다.


장점 : 인덱스를 이용한 데이터의 직접적인 접근이 가능하다.


단점 : 삽입, 삭제 시에 다른 데이터들의 위치를 바꿔줘야 한다.


연결리스트(Linked List)

탐색 : 인덱스를 이용하여 직접 접근이 불가능하다. 머리(Head)부터 순차적으로 접근해야 한다.


삽입 : 삽입할 노드를 만든 다음 삽입할 위치의 앞의 노드의 포인터가 삽입할 노드를 가리키게한다. 이어질 노드는 삽입한 노드의 포인터가 가르키게한다.터가 가르키게한다.


삭제 : 삭제할 노드가 가르키는 노드를 이전 노드의 포인터가 가르키게한다. 삭제할 노드의 메모리를 해제한다.


장점 : 데이터의 삽입, 삭제 시에 데이터의 이동이 없다.


단점 : 자료에 직접적으로 접근을 할 수가 없다. 또한 노드를 가르키는 포인터로인해 메모리를 더 사용한다.




●스택

-한 쪽에서만 삽입, 삭제가 일어난다.

-가장 위쪽을 가르키는 포인터를 TOP이라고 한다.

-한 쪽 끝에서만 삽입, 삭제가 일어나기 때문에 가장 나중에 삭제된 테이터가 제일 먼저 삭제된다.


스택 - Overflow와 Underflow

오버플로우(Overflow) : 스택이 가득 차 있는 상태에서 Push(삽입)작업을 하면 발생한다.

언더플로우(Underflow) : 스택이 비어 있는 상태에서 Pop(삭제)작업을 하면 발생한다.




●큐

-한 쪽에서 삽입이 일어나고 다른 끝에서 삭제가 일어나는 자료구조

-삽입이 일어나는 끝을 가르키는 포인터를 Rear라고 한다.

-삭제가 일어나는 끝을 가르키는 포인터를 Front라고 한다.

-가장 먼저 삽입된 데이터가 가장 먼저 삭제된다.


큐 - Overflow와 Underflow

오버플로우(Overflow) : 큐가 가득 차 있는 상태에서 Insert(삽입)작업을 하면 발생한다.

언더플로우(Underflow) : 큐가 비어 있는 상태에서 Remove(삭제)작업을 하면 발생한다.




●트리

-계층적 구조를 나타내는 자료구조

-컴퓨터 디스크의 구조, 인공지능의 결정트리에 이용


트리의 객체(Object)

루트노드 : 트리의 최상단 노드

부모노드 : 해당 노드의 위에 연결된 노드

자식노드 : 해당 노드의 밑에 연결된 노드

형제노드 : 같은 부모노드에 연결되어 있는 노드


트리의 종류

이진 트리 : 각 노드의 자식노드의 수가 2이하인 트리


완전이진 트리 : 이진트리 중에 마지막 레벨을 제외한 모든 레벨의 노드가 최대의 수를 충족하고 마지막레벨은 왼쪽부터 마지막 노드까지 가득 차있는 트리


경사 트리 : 왼쪽 혹은 오른쪽으로 노드들이 한 쪽 방향으로 치우친 트리


트리의 표현방법

배열 : 거의 채워져 있는 이진트리를 구현할 때, 탐색이 용이하고 구현이 간편하며 메모리활용이 효율적이다.


연결리스트 : 노드가 거의 채워지지 않은 트리 혹은 경사트리를 구현할 때 효율적이다.


트리의 변형

이진탐색트리

AVL 트리

2-3 트리

2-3-4 트리




●그래프

-연결되어 있는 객체 간의 관계를 표현하는 자료구조

-최단거리나 최대, 최소비용을 구할 때, 그래프를 이용한 신장트리 사용


그래프의 객체(Object)

정점(Vertax) : 그래프의 각 객체, 노드

간선(Edge) : 그래프의 각 객체를 잇는 간선, 링크라고도 부른다.


그래프의 종류

무방향 그래프 : 간선을 통하여 양방향으로 갈 수 있음.

방향 그래프 : 간선을 통해 한 쪽 방향으로만 갈 수 있음.


그래프의 탐색방법

깊이우선탐색(DFS) : 재귀호출을 이용한 묵시적 스택 사용을 이용한 방법

너비우선탐색(BFS) : 큐를 이용한 탐색방법 가까운 정점부터 방문하는 방법




+ Recent posts