sagecode 님의 블로그

데이터베이스에서 index는 데이터를 빠르게 찾을 수 있게 도와주는 자료구조입니다. 테이블에 index를 만약에 설정하지 않는다면 최악의 경우 모든 데이터를 다 조회해야하는 O(n)의 시간복잡도가 나올 수 있다. 하지만 인덱스를 도입하게 되면 O(log n)까지 줄일 수 있습니다. 그 이유는 index가 B-tree 자료구조로 형성되어 있기 때문입니다. B-tree 는 Balanced Tree라고 하며, 균형 다진 탐색 트리라고 한다. 모든 리프 노드의 차수가 동일하므로, 트리 높이가 일정하게 유지됩니다. 또한, B-Tree는 각 노드가 여러 개의 키(key)와 자식 포인터를 가질 수 있는 트리 구조입니다. 검색할 때는 루트 노드부터 시작하여 현재 노드의 키와 비교하면서 범위를 좁혀가며 탐색합니다. 이러..

데이터를 효율적으로 저장하고 검색하기 위해 다양한 트리 자료구조(Tree Structure)가 사용된다. 그중에서도 이진 트리와 레드블랙 트리는 많은 프로그래밍 환경에서 자주 등장한다. Java Collection에서 트리 맵(Tree Map), 트리 셋(Tree Set)의 경우 레드블랙 트리를 사용한다. 그럼 이진트리와 레드블랙 트리는 어떤점이 다를까? 이진 트리(Binary Tree)란?이진 트리는 모든 노드가 최대 두 개의 자식 노드(left, right)를 가지는 트리 구조이다. 10 / \ 5 15노드 : 트리 구조의 기본 단위로, 값(data)을 저장하고 다른 노드와의 연결을 가짐루트(Root) 노드 : 트리의 제일 위에 있는 시작 노드자식 노드 : 어떤 노드의 아래에 연결된..