교대최소제곱법
[자료구조] B- 트리란? 본문
B- tree가 무엇인가?
자료구조 중 하나
이진트리와 다르게 하나의 노드에 최대 M개의 자식을 가지는 트리
예를들어 값이 [10, 20]이 있으면
10보다 작은 서브트리, 10과 20 사이의 서브트리, 20보다 큰 서브트리 이렇게 3개의 자식이 생기는 트리가 B-트리이다.
삽입의 경우 M개의 제한을 걸어두고 값이 M개 이상이 되면 (노드는 최대 M-1개 까지 값을 가질 수 있다) 분할이 이루어진다
분할 과정은 가운데 값이 부모 노드로 올라가서 합쳐지는 방식으로 부모노드도 초과할 경우 계속 올라가는 방식으로 삽입이 진행된다
삭제는 더 어렵다, 자세한 것은 블로그 참조
[자료구조] 그림으로 알아보는 B-Tree
B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리입니다.
velog.io
B- 트리의 업그레이드
B- 트리는 M개의 자식을 가지게 되면서 이진트리의 상위호환이 되었지만 구조를 유지하기 위해서 추가적인 연산이 수행되거나 새로운 노드가 생성된다는 단점이 있다.
그래서 이러한 연산과 추가적인 노드 생성을 최소화하기 위해 몇 가지 규칙이 추가된 것이 B* tree이다
또한 B- 트리의 경우 탐색을 위해 노드를 찾아 이동해야 한다는 단점이 있었다
이러한 단점을 해결하고자 B+ 트리이고 기본적인 아이디어는 같은 depth까지 이동 후 같은 레벨의 노드를 연결리스트로 연결시켜 탐색한다라는 아이디어이다.
부모 자식을 왔다갔다 하면서 찾는 B- 트리보다는 훨씬 유리하다
있을지 없을지 모르는 탐색을 하는 B- 트리보다는 무조건 존재하는 B+ 트리가 효율적이기 때문에 오늘날 데이터베이스들은 B+ 트리 구조를 채택한다.
[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree
[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree
위 글을 보고 정리를 하지 않을 수 없었습니다. 가슴이 시키네요;; 그렇다면 바로 B-Tree, B*Tree, B+Tree의 특징에 대해서 알아봅시다. 목차 0. 이진트리 B-Tree, B*Tree, B+Tree에 대해서 알아보자면서 갑자
ssocoit.tistory.com
'CS 기초 > 자료구조' 카테고리의 다른 글
[자료구조] 파이썬 heapq 라이브러리는 어떻게 구현될까? (0) | 2023.10.24 |
---|---|
[자료구조] 해시 테이블의 모든 것 (1) | 2023.10.18 |
[자료구조] 자료구조 정리 및 정렬 알고리즘 (1) | 2023.10.16 |