데이터베이스에서 index는 데이터를 빠르게 찾을 수 있게 도와주는 자료구조입니다. 테이블에 index를 만약에 설정하지 않는다면 최악의 경우 모든 데이터를 다 조회해야하는 O(n)의 시간복잡도가 나올 수 있다. 하지만 인덱스를 도입하게 되면 O(log n)까지 줄일 수 있습니다. 그 이유는 index가 B-tree 자료구조로 형성되어 있기 때문입니다. B-tree 는 Balanced Tree라고 하며, 균형 다진 탐색 트리라고 한다. 모든 리프 노드의 차수가 동일하므로, 트리 높이가 일정하게 유지됩니다. 또한, B-Tree는 각 노드가 여러 개의 키(key)와 자식 포인터를 가질 수 있는 트리 구조입니다. 검색할 때는 루트 노드부터 시작하여 현재 노드의 키와 비교하면서 범위를 좁혀가며 탐색합니다. 이러..