왜 ?? 인덱싱을 사용하면 조회 속도가 빨라질까 ?
여기 눌러 확인
위 링크에 이전 정리해놓은 글이 있긴 하지만 너무 허접하다, 링크에 들어가서 확인 하기 귀찮기도 하고 간단하게 말한다면.
검색하고자 하는 테이블의 Index가 설정된 열에서 Where의 주소를 먼저 취합 후 테이블에서 해당 주소들을 바탕으로 행을 찾아낸다.
※ 주소와 함께 행을 같이 취합하는 Covering Inde(커버링 인덱스) 라는 개념도 있다.
그러면 어떻게 위와 같이 동작할 수 있을까?
Balanced Tree
- 균형 트리로 불리는 동작은 데이터를 찾아가는 과정 중 Node 들의 균혀을 유지하면서 찾아가는 방식
그렇기 때문에 값의 정렬을 하고 중간값을 기준으로 한다는 특징이 있다.
만약 70이라는 데이터를 찾고 싶다면 ??
[10, 20, 30, 40, 50, 60, 70, 80] [40]
/ \
[20] [60]
/ \ / \
[10] [30] [50] [70, 80] 위와 같은 동작 방식으로 3번 만에 70을 찾을 수 있다.
(Full Scan하면 7번 확인 해야한다)
즉, 중간값 비교 검증을 해 나가기 때문에 빠른 데이터 검색이 가능하다.
1. B-Tree
Balancd Tree의 기본 방식 정렬 후 중간 값 비교 검증을 통한 찾고자 하는 데이터를 찾는 방법.
그러나 찾고자 하는 데이터를 찾아가는 과정 중 각 중간노드(Internal Node)에 데이터들이 저장되어 있다...
즉, 비효율이 발생한다는 말이고 이것을 개선 한 것이 B+Tree 이다.
2. B+Tree
리프노드(Leaf Node) : 더 이상의 자식노드가 없는 End Point Node
중간노드(Internal Node) : 리프노드를 찾아가는 과정의 중간과정의 노드
B+Tree 는 중간노드(자식노드가 있는 노드)에서는 목적지를 찾아가는데 필수적인 키 값만 알고 있다.
실질적인 데이터 및 링크 정보 등은 Leaf Node 에 저장이 되어 효율적인 검색이 가능하게 한다.
결론
-
Index
테이블에서 인덱스가 설정된 열을 기반으로 조건을 먼저 찾고, 그 후 해당 조건에 맞는 데이터의 행을 빠르게 조회.
-
Balanced Tree
B-Tree는 데이터를 정렬된 상태로 유지하고, 루트 노드부터 시작해 중간값(키 값)을 기준으로 좌우로 분기하며 원하는 값을 찾아가는 트리 구조.
-
B-Tree vs B+Tree
B-Tree는 모든 노드에 데이터가 저장되지만, B+Tree는 리프 노드에만 데이터를 저장하고 나머지는 키 값(경로 안내) 저장.
항목 B-Tree B+Tree 데이터 저장 위치 모든 노드에 저장 가능 리프 노드에만 데이터 저장 중간 노드 데이터 + 키 값 둘 다 저장 가능 키 값만 저장 (검색용 경로 안내 역할) 리프 노드 다른 노드와 연결 X 리프 노드끼리 연결되어 있어 범위 검색에 유리 검색 속도 깊이에 따라 달라짐 모든 데이터가 리프에 있어 균일한 검색 속도 범위 검색 느릴 수 있음 리프 노드 연결로 빠름 구조 트리형 구조 트리 + 연결 리스트 구조
