[MySQL] Index, Tree

Dev/SQL

syuare 2025. 4. 11. 22:45

[내일배움캠프][SQL] Lv1. 데이터 속 김서방 찾기

Table - users > 스파르타 코딩클럽에 가입한 유저들의 정보를 날짜별로 기록한 테이블user_id: 익명화된 유저들의 아이디(varchar255)created_at: 아이디 생성 날짜(timestamp)updated_at: 정보 업데이트 날

syuare.tistory.com

SQL 달리기반 퀘스트를 진행 중에 여러 개념이 있길래 별도로 정리해보았다.

데이터베이스 테이블에 있는 데이터를 빠르게 검색할 수 있도록 만들어진 자료구조

인덱스는 일반적으로 B-트리 / B+트리 구조를 사용함

정렬된 데이터 저장:
- 인덱스는 특정 컬럼의 값을 정렬된 상태로 저장함
  - 예를 들어 "김%"와 같이 문자열의 시작 부분을 조건으로 검색할 때, 인덱스는 범위 검색(range scan)을 통해 필요한 데이터만 빠르게 찾아낼 수 있음
포인터 역할:
- 인덱스의 각 엔트리는 실제 테이블의 행에 대한 포인터(주소)를 포함함
  - 인덱스를 통해 특정 값의 위치를 찾은 후, 해당 포인터를 사용하여 실제 데이터를 읽어옴
검색 시간 단축:
- 인덱스가 있으면, 전체 테이블을 순차 탐색하는 대신 트리 구조를 따라 탐색하게 되므로 검색 시간이 로그 시간(logarithmic time)으로 단축

대용량 데이터베이스와 파일 시스템에서 사용

디스크 I/O를 최소화하면서 많은 데이터를 정렬된 상태로 저장하여 빠른 검색 및 범위 검색을 지원

        [10 | 20]
       /    |    \
  [5]   [15]   [25 | 30]
-- 10, 20은 루트에 데이터로 직접 존재하고, 리프 노드들도 각각 데이터를 가짐.

        [10 | 20]
       /    |    \
  →[1|5]→[11|15]→[21|25|30]→
-- 루트(내부 노드)는 10, 20 기준값만 가지고 있고, 
-- 실제 데이터는 리프 노드에만 있음. 리프들은 오른쪽으로 쭉 연결되어 있음

특성	B-트리	B+ 트리
데이터 저장 위치	내부 노드와 리프 노드 모두 데이터(키 및 값)를 저장	내부 노드에는 키만 저장하고, 실제 데이터는 모든 리프 노드에 저장
노드 연결	리프 노드 간 별도의 연결이 없는 경우가 일반적	리프 노드들이 연결 리스트로 서로 링크되어 있어 순차 검색이 용이
범위 검색	범위 검색은 가능하지만, 리프 노드가 연결되어 있지 않아 순차 접근이 덜 효율적일 수 있음	리프 노드가 연결되어 있어 범위 검색 및 정렬된 순서대로 데이터 접근에 유리
내부 노드 크기 최적화	키와 데이터를 모두 저장하므로, 노드 당 저장할 수 있는 항목 수가 상대적으로 줄어들 수 있음	내부 노드에는 키만 저장하므로, 한 노드에 더 많은 키를 저장할 수 있어 트리의 높이를 더 낮출 수 있음

루트(Root) 노드에서 시작해 계층적 관계를 갖는 노드들의 집합으로,

사이클(cycle)이 없고 계층구조를 이루는 비선형 자료구조