개요
2-3 트리는 키를 정렬된 순서로 저장하는 다원 탐색 트리다. 키 하나를 가진 2-노드와 키 두 개를 가진 3-노드로 구성된다. 내부 노드의 자식은 각각 두 개와 세 개이며, 모든 리프가 같은 깊이에 놓이는 높이 균형 조건을 만족한다.
탐색
키 하나인 노드에서는 그 키보다 작은 범위와 큰 범위로 탐색 경로를 나눈다. 키 두 개인 노드에서는 작은 키보다 작은 범위, 두 키 사이, 큰 키보다 큰 범위의 세 경로로 나뉜다. 루트부터 해당 범위의 자식으로 이동해 탐색한다.
삽입과 분할
새 키는 적절한 리프 위치에 삽입한다. 키가 세 개가 되어 허용 크기를 넘으면 가운데 키를 부모로 올리고 나머지를 두 노드로 분리한다. 부모에서도 초과가 생기면 분할이 위로 전파된다. 루트가 분할될 때는 새 루트를 생성해 트리 전체의 높이가 한 단계 증가한다.
높이와 접근 비용
높이 균형과 내부 노드의 최소 두 자식 조건에 따라 탐색과 갱신의 시간 복잡도는 로그 수준이다. 디스크 기반 구현의 접근 횟수는 이 시간 복잡도와 별도다. 노드와 블록의 대응, 루트 등의 캐시 여부, 분할 후 쓰기와 새 블록 할당을 계산에 포함하는지에 따라 실제 또는 문제상의 입출력 횟수가 달라진다.