[자료구조]TREE &SEARCH & HASH

소개

트리와 탐색, 해쉬에 대해서 전반적으로 조사되어 있습니다. 특히 잘 찾기 힘든 B트리와 B+트리에 대해서 자세히 나와있어서 컴퓨터 관련 과목을 수강하는 학생에게 큰 도움이 될 수 있습니다.

목차

1. 트리의 정의

2. 트리의 조건

3. 트리의 종류
3.1 자유 트리
3.2 순서 트리(Ordered Tree)
3.3 비순서 트리(Oriented Tree)
3.4 닮은 트리(Similar Tree)
3.5 대등 트리(Equivalent Tree)

4. B-Tree
4.1 정의
4.2 새로운 노드 삽입 알고리즘
4.3 노드 삭제 알고리즘

5. B+트리
5.1 정의
5.2 특징 (B-트리와의 차이점)

6. 해싱
6.1 정의
6.2 정적 해싱의 종류
6.3 동적 해싱

본문내용

- B-트리는 탐색 시에 반드시 리프 노드에 도달하지 않더라도 원하는 값을 찾을 수 있다. 그러나 B+트리는 항상 뿌리로부터 어떤 리프 노드까지의 길을 답사해야만 한다. 그렇게 보면 B-트리가 B+트리보다 더 빠르게 보인다. 그러나 B+트리는 근노드와 간노드 (합쳐서 internal node, 리프노드를 제외한 모든 노드) 안에 있던 Data Pointer가 삭제되어 있다. 왜냐하면 리프 노드에 모든 실제 데이터가 있고, 인덱스 세트는 단지 리프 노드의 킷값을 찾아갈 수 있도록 하는 경로로만 사용되기 때문에 Data Pointer 가 필요하지 않게 된 것이다.일반적으로 m-값이 커질수록 트리의 높이가 낮아지면서 더 빨리 검색할 수 있게 된다. 또한 트리의 균형을 일부러 맞추는 이유도 가능한 한 높이를 낮추어 더 빨리 찾게 하기 위해서이다. 우리가 'm-원 탐색' 에서 살펴보았듯이 이 m 값은 한번의 I/O Operation 안에서 가능한 한 최대의 크기를 잡아야 한다. 그렇다고 무작정 크게 잡을 수도 없는 것이 한번의 I/O Operation 시에 읽을 수 있는 블록 사이즈에는 한계가 있기 때문이다. (예를들어 4096Byte등) 이것을 무시하고 무작정 크게 잡게 되면 트리의 높이 1단계를 지날 때마다 1번이 아니라 여러번의 I/O 가 발생하게 되어 검색속도가 1/2, 1/3로 떨어지게 된다.B+트리는 데이터 포인터가 없어졌기 때문에 남은 용량이 있게 되었는데, 이 용량에 킷값과 레코드 포인터를 넣어 m값을 1만 늘려도 트리 전체높이에 중대한 변화가 생기게 된다. m=4 인 트리와 m=5인 트리를 생각해보자.

참고자료

· 없음