엘리
테이블에서 레코드들에 대한 검색 속도를 높이기 위해, 레코드에 대한 물리적 저장 위치를 별도로 기록한 자료 구조이다.
책의 목차나 맨 뒷 페이지의 찾아보기와 유사한 개념이다.
모든 레코드들을 순차적으로 검색해서 원하는 데이터를 찾아야한다. = Full Table Scan
MySQL에서 사용하는 B+ Tree Index를 기준으로 설명한다.
- 데이터의 정렬을 전제로한다.
- 데이터 탐색 시 O(log2 N)의 시작 복잡도를 보장한다.
- Binary Search Tree와 유사하지만 한 노드 당 자식 노드가 2개 이상일 수 있다.
- B+ Tree는 B Tree의 확장 개념으로,
- 오직 리프 노드에만 key와 data를 모두 저장하고 다른 노드에는 key만 저장한다.
- 모든 리프 노드가 Linked List로 연결되어 있다.
- https://mangkyu.tistory.com/96
- https://velog.io/@sjy5386/DB%EC%97%90%EC%84%9C-Index%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%B4-%EB%8D%B0%EC%9D%B4%ED%84%B0%EC%97%90-%EC%A0%91%EA%B7%BC%ED%95%98%EB%8A%94-%EA%B3%BC%EC%A0%95
- https://kyungyeon.dev/posts/66
- https://zorba91.tistory.com/293
- https://siahn95.tistory.com/entry/DB-%EC%9D%B8%EB%8D%B1%EC%8A%A4%EB%9E%80-3-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EC%8A%A4%EC%BA%94-%EB%B0%A9%EC%8B%9D-%EA%B0%9C%EB%85%90?category=821999
네, 인덱스는 인덱스를 적용한 컬럼의 값을 나타내는 key와 데이터의 실제 물리적 위치 주소를 테이블 외의 별도 저장 공간에 저장합니다. 따라서 무조건 별도의 저장 공간이 필요하며, 보통 테이블의 10% 정도를 차지한다고 합니다.
클러스터드 인덱스의 경우 별도의 저장 공간이 필요하지 않다고 생각할 수 있지만, 리프 노드에 대한 별도 저장 공간이 필요하지 않은 것이지 루트 노드와 인터널 노드에 대한 별도 저장 공간은 필요합니다.
- 클러스터드 인덱스의 리프 노드는 실제 테이블의 데이터이기 때문에 별도 저장 공간이 필요하지 않습니다.