파일처리 썸네일형 리스트형 B+ 트리 개념 모든 레코드들이 트리의 최하위 레벨에 정렬되어 있고 트리 내부 블록에는 키들만 저장됨. 파일시스템 같은 블록기반 스토리지에서 저장데이터의 효율적인 검색에 유용함. 알고리즘 검색 Function: search (k) return tree_search (k, root); Function: tree_search (k, node) if node is a leaf then return node; switch k do case k < k_0 return tree_search(k, p_0); case k_i ≤ k < k_{i+1} return tree_search(k, p_i); case k_d ≤ k return tree_search(k, p_d); 삽입 1. 새 레코드를 삽입하기위한 검색을 수행 2. 노드.. 더보기 B트리 특징 및 개념 정렬된 데이터 보존. 로그시간내에 검색, 순차접근, 삽입, 삭제가 가능. 노드가 가득차 있지 않기 때문에 일정부분의 공간이 낭비됨. 모든 리프노드가 같은 깊이를 가지게 됨. B트리의 노드들은 여러개의 키를 가지고 있고, 이 키를 기준으로 하위트리들을 나누게 됨. 자식노드의 개수는 키개수+1 이 됨. 정의 각 노드의 키값은 하위트리들을 나누는 값이 되어야 함. 차수가 m인 B 트리는 다음 속성들을 만족시켜야 함. 1. 모든 노드는 최대 m 개의 자식들을 가져야한다. 2. 리프노드가 아닌 모든 노드(루트노드 제외)는 최소한 m/2개의 자식을 가져야 한다. 3. 루트 노드는 최소한 2개의 자식을 가져야 한다. 4. k개의 자식을 가지고 있는 리프노드가 아닌 노드는 k-1개의 키를 가진다. 5. .. 더보기 이전 1 다음
