데이터베이스 인덱스는 왜 'B-Tree'를 선택 했을까?

B-Tree란?B-Tree는 기존 이진 탐색 트리에서 최악의 경우 시간 복잡도가 O(N)이 되는 문제를 해결하기 위해, 노드들이 한쪽으로 치우치지 않도록 균형을 유지하도록 설계된 트리이다. 그렇다면 데이터베이스 인덱스는 왜 B-tree를 선택 했을까? 배열을 사용하지 않는 이유데이터베이스에 수십억건의 대량의 데이터가 저장될 수 있는데, 이를 배열로 관리하면 메모리에 모든 데이터를 한 번에 올려야 하므로 비효율적이다.또한 삽입, 삭제시 최악의 경우 O(N)으로 비효율적이다. 연결 리스트를 사용하지 않는 이유연결 리스트의 경우 배열의 단점인 삽입, 삭제시 시간복잡도가 O(1)로 효율적이다.하지만 연결 리스트의 경우 조회시 최악의 경우 시간 복잡도가 O(N)으로 비효율적이다. 해시 테이블을 사용하지 않는 이유..
내생각 2025. 5. 26. 15:34
1