트리 자료구조

이진 탐색은 전제조건이 데이터 정렬이다.

 

데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리(Tree)자료구조를 이용하여 항상 데이터가 정렬되어 있다.

 

데이터베이스에서의 탐색은 이진 탐색과는 조금 다르지만, 이진 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있어 데이터가 많아도 탐색하는 속도가 빠르다.

 

트리자료구조란?

 

노드와 노드의 연결로 표현하며 여기에서 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있다.

 

트리자료구조는 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용한다. 

트리자료구조는 몇가지 주요한 특징이 있다.

• 트리는 부모 노드와 자식 노드의 관계로 표현된다.
• 트리의 최상단 노드를 루트 노드라고 한다.
• 트리의 최하단 노드를 단말 노드라고 한다.
• 트리에서 일부를 떼어내도 트리구조이며 이를 서브트리라 한다.
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

소프트웨어는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능하다.