📍B-Tree
🔎 B-Tree 정의
B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리이다.
정렬된 순서를 보장하고, 멀티레벨 인덱싱을 통한 빠른 검색을 할 수 있기 때문에 DB에서 사용하는 자료구조 중 한 종류이다.
🔎 B-Tree 특징
- 균형이진트리의 연속: 아무리 최악의 경우라도 O(logN)의 검색 성능
- 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다.
- 각 노드의 자료는 정렬되어 있다.
- 자료는 중복되지 않는다.
- 모든 leaf node는 같은 레벨에 있다.
- root node는 자신이 leaf node가 되지 않는 이상 적어도 2개 이상의 자식을 가진다.
- root node와 leaf node를 제외한 노드들은 최대 M개부터 최소 ⌈M/2⌉개 까지의 자식을 가질 수 있다.
- 노드의 키는 최대 M-1개부터 최소 ⌈M/2⌉ - 1개의 키가 포함될 수 있다.
- 자식 수의 하한값을 t라고 하면, M = 2t - 1 을 만족한다.
파란색 부분은 각 노드의 key를 나타내며, 빨간색 부분은 자식 노드들을 가르키는 포인터이다. key들은 노드 안에서 항상 정렬된 값을 가지며, 이진검색 트리처럼 각 key들의 왼쪽 자식들은 항상 key보다 작은 값을, 오른쪽은 큰 값을 가진다.
🔎 B-Tree 확인해보기
📍B+Tree
🔎 B+Tree 정의
- B트리와 굉장히 유사하지만 리프노드는 연결리스트의 형태를 띄어 선형 검색이 가능한 트리이다.
🔎 B+Tree 특징
- 데이터 노드의 자료는 정렬되어 있다.
- 데이터 노드에서는 데이터가 중복되지 않는다.
- 모든 leaf node는 같은 레벨에 있다.
- leaf node가 아닌 node의 키값의 수는 그 노드의 서브 트리 수보다 하나가 적다.
🔎 B-Tree와의 차이
- 모든 key, data가 리프노드에 모여있다. B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가진다.
- 모든 리프노드가 연결리스트의 형태를 띄고 있다. B트리는 옆에있는 리프노드를 검사할 때 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어든다.
- 리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같다.
🔎 B+Tree 확인해보기
📍스터디 회고
🔎 아쉬운 점
생각보다 공부할 내용이 많아서 자세하게 하지 못한게 아쉬웠다.
추가로 더 공부해 봐야겠다
🔎 추가로 알게 된 내용
🔎 추가로 공부할 내용
📍공부한 곳
https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree
https://code-lab1.tistory.com/217
https://ssocoit.tistory.com/217
공부하자