익명 사용자
로그인하지 않음
토론
기여
계정 만들기
로그인
IT 위키
검색
B+ 트리
편집하기
IT 위키
이름공간
문서
토론
더 보기
더 보기
문서 행위
읽기
편집
원본 편집
역사
경고:
로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다.
로그인
하거나
계정을 생성하면
편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.
스팸 방지 검사입니다. 이것을 입력하지
마세요
!
'''B+ 트리'''(B+ Tree)는 B 트리(B-Tree)의 확장된 버전으로, 데이터베이스 및 파일 시스템에서 효율적인 검색 및 범위 쿼리를 수행하는 데 사용된다. B+ 트리는 모든 키를 리프 노드(Leaf Nodes)에 저장하며, 리프 노드끼리는 연결 리스트(Linked List)로 연결되어 있다. ==개요== B+ 트리는 B 트리와 유사하지만 몇 가지 중요한 차이점이 있다. *'''리프 노드에만 키와 데이터 저장''' **내부 노드(Internal Nodes)는 탐색을 위한 인덱스 역할만 수행하고, 실제 데이터는 리프 노드에 저장된다. *'''리프 노드 연결 리스트''' **리프 노드끼리 연결 리스트(Linked List) 형태로 연결되어 있어 범위 검색(Range Query)이 매우 빠르다. *'''균형 유지''' **모든 리프 노드는 동일한 깊이를 가지며, 항상 균형을 유지한다. ==B+ 트리의 속성== 1. 내부 노드는 키만 저장하며, 실제 데이터는 리프 노드에만 저장된다. 2. 리프 노드는 이중 연결 리스트(Double Linked List) 형태로 연결되어 있다. 3. 각 노드는 최소 ⌈m/2⌉개의 자식과 최대 m개의 자식을 가질 수 있다. 4. 모든 리프 노드는 동일한 깊이에 존재한다. 5. 검색, 삽입, 삭제 연산의 시간 복잡도는 O(log n)이다. {| class="wikitable" |+B+ 트리의 특징 !속성!!설명 |- |키 저장 위치||리프 노드에만 저장 |- |내부 노드 ```mediawiki ||인덱스 역할만 수행 |- |리프 노드 연결||연결 리스트로 연결되어 있음 |- |탐색 성능||빠름 (리프 노드에서만 탐색) |- |범위 검색||매우 빠름 (리프 노드 간 연결 이용) |} ==B+ 트리 vs B 트리== B+ 트리와 B 트리는 유사하지만 몇 가지 중요한 차이점이 있다. {| class="wikitable" |+B+ 트리와 B 트리 비교 !기준!!B 트리!!B+ 트리 |- |키 저장 위치||내부 노드와 리프 노드||모든 키가 리프 노드에 저장 |- |탐색 속도||느림 (내부 노드에서도 탐색)||빠름 (리프 노드에서만 탐색) |- |범위 검색||상대적으로 비효율적||빠름 (리프 노드 연결 리스트 사용) |- |리프 노드 연결||X||O (이중 연결 리스트) |} ==B+ 트리 연산== ===1. 삽입 (Insertion)=== 1. 적절한 리프 노드를 찾아 삽입한다. 2. 노드가 초과(m개의 키)되면 중앙 키를 상위 노드로 올리고, 노드를 분할한다. ===2. 삭제 (Deletion)=== 1. 삭제 후 노드에 남아 있는 키 개수를 확인한다. 2. 최소 키 개수보다 적으면 형제 노드에서 빌리거나, 병합을 수행한다. ===3. 검색 (Search)=== 1. 루트에서 시작하여 적절한 자식 노드를 따라가며 키를 찾는다. 2. O(log n)의 시간 복잡도로 검색 가능하다. ==B+ 트리 구현 (Python)== <syntaxhighlight lang="python"> class BPlusTreeNode: def __init__(self, leaf=False): self.leaf = leaf self.keys = [] self.children = [] self.next = None # 리프 노드 연결 리스트 class BPlusTree: def __init__(self, t): self.root = BPlusTreeNode(True) self.t = t # 최소 차수 def search(self, node, key): i = 0 while i < len(node.keys) and key > node.keys[i]: i += 1 if node.leaf: if i < len(node.keys) and key == node.keys[i]: return node return None return self.search(node.children[i], key) def insert(self, key): root = self.root if len(root.keys) == (2 * self.t) - 1: new_root = BPlusTreeNode(False) new_root.children.append(self.root) self.split_child(new_root, 0) self.root = new_root self.insert_non_full(new_root, key) else: self.insert_non_full(root, key) def insert_non_full(self, node, key): i = len(node.keys) - 1 if node.leaf: node.keys.append(None) while i >= 0 and key < node.keys[i]: node.keys[i + 1] = node.keys[i] i -= 1 node.keys[i + 1] = key else: while i >= 0 and key < node.keys[i]: i -= 1 i += 1 if len(node.children[i].keys) == (2 * self.t) - 1: self.split_child(node, i) if key > node.keys[i]: i += 1 self.insert_non_full(node.children[i], key) def split_child(self, node, i): t = self.t y = node.children[i] z = BPlusTreeNode(y.leaf) node.keys.insert(i, y.keys[t - 1]) node.children.insert(i + 1, z) z.keys = y.keys[t:(2 * t - 1)] y.keys = y.keys[0:(t - 1)] if not y.leaf: z.children = y.children[t:(2 * t)] y.children = y.children[0:t] if y.leaf: z.next = y.next y.next = z def traverse(self, node): if node.leaf: while node: print(node.keys, end=" → ") node = node.next print("None") else: for i in range(len(node.keys)): self.traverse(node.children[i]) self.traverse(node.children[len(node.keys)]) # B+ 트리 테스트 bplustree = BPlusTree(3) # 최소 차수 t = 3 for key in [10, 20, 5, 6, 12, 30, 7, 17]: bplustree.insert(key) print("B+ 트리 리프 노드 순회 결과:") bplustree.traverse(bplustree.root) print("\n") </syntaxhighlight> ==같이 보기== *[[B 트리]] *[[이진 검색 트리]] *[[AVL 트리]] *[[트리 (자료 구조)]] ==참고 문헌== *Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). ''Introduction to Algorithms''. MIT Press. *[https://www.geeksforgeeks.org/b-plus-tree-set-1-introduction/ GeeksforGeeks - B+ Tree Introduction] [[분류:알고리즘]] [[분류:트리]]
요약:
IT 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 라이선스로 배포된다는 점을 유의해 주세요(자세한 내용에 대해서는
IT 위키:저작권
문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요.
또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다.
저작권이 있는 내용을 허가 없이 저장하지 마세요!
취소
편집 도움말
(새 창에서 열림)
둘러보기
둘러보기
대문
최근 바뀜
광고
위키 도구
위키 도구
특수 문서 목록
문서 도구
문서 도구
사용자 문서 도구
더 보기
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
문서 기록