B+Tree1 BST / B tree / B+tree관련정보 Mysql을 공부하던 중, Mysql의 스토리지 엔진인 InnoDB에서는 인덱스를 관리할 때 B+tree 방식을 사용한다고 한다. 그래서 해당 방식을 차용하게 된 과정을 거슬러올라가며 개념을 정리하고자 한다! 그러기 위해서 우선 이진탐색 트리(BST)부터 시작하고자 한다. (자료는 점점 채워나갈 예정이다 ㅎㅎㅎ..) 이진탐색 트리 (BST) 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값만 가지며, 오른쪽 서브트리는 큰 값만 가지는 형태 > 특징 1. 자녀 노드는 최대 2개까지만 가능 > 시간 복잡도 편향 트리일 땐 O(logN), 일반적일 땐 O(logN) BST의 해당 특징 및 시간복잡도로 인해서 선대 개발자님들은 고민을 하게 되었다. 1. 어떻게 하면 자녀 노드를 최대 2개가 아닌, 여러.. 2023. 3. 15. 이전 1 다음
