힙 정렬(Heap Sort)과 B Tree

힙 정렬(Heap sort)이란

1. 원소들을 전부 힙에 삽입한다.
2. 힙의 루트에 있는 값은 남은 수들 중에서 최솟값(혹은 최댓값)을 가지므로 루트를 출력하고 힙에서 제거한다.
3. 힙이 빌 때까지 2의 과정을 반복한다.

힙 정렬 예시

B Tree

B Tree는 이진 트리를 확장한 것으로 이진 트리는 하나의 노드가 가질 수 있는 자식 노드의 수가 최대 2개지만

B-tree는 2개 이상을 가질 수 있다

모든 노드에 있는 값들은 정렬되어 있는 상태이며 order를 나타내는 숫자인 m을 가질 수 있다

이 B-tree 를 B-tree of order m 이라고 한다

 

B-tree of order m은 다음과 같은 조건을 만족 시킨다.

• 모든 노드가 가질 수 있는 자식 노드의 최대 수는 m이다.
• 루트 노드를 제외한 내부 노드 들은 적어도 [m/2]개의 자식 노드를 가진다.
• 루트 노드는 최소한 두개의 자식 노드를 가진다.
• k개의 자식 노드를 가진 내부 노드들은 k-1개의 값을 가지고 있다
• 모든 리프 노드들의 높이는 같다
• 중복 값이 없다

데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다

(B-tree의 확장형인 B+ tree를 쓰기도 함)

 

메모리가 파일 시스템에 Access할 때, 그 횟수를 줄이기 위해서 사용되기도 한다

(많은 파일을 인덱싱해두면 접근할 때의 시간을 줄일 수 있음)

 

파일들을 인덱싱할 때, B Tree를 쓰게 되면

그냥 트리 구조보다 Depth를 줄일 수 있다는 이점이 있다

 

데이터베이스의 정보에 대해서 테이블의 특정 column에 대해서 인덱싱을 하면

그 column에 대한 인덱스 테이블이 생긴다

그 후, 그 테이블에 대해서 해당 column을 조건으로 select할 때

먼저 인덱스 테이블을 참조하므로 퍼포먼스를 높일 수 있다

 

참고 사이트

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Data Structure Visualization

https://www.geeksforgeeks.org/heap-sort/?ref=lbp 

Heap Sort - GeeksforGeeks

 

SSS