동전 주머니가 5자루 있다. 각 주머니마다 동전이 10개씩 들어있다. 잘 만들어진 동전은 하나당 10g 이고, 불량 동전은 11g이다. 5자루 중 한 주머니가 불량품 동전만 들어있다는 것을 알게 됬다.
이 때 저울을 몇 번 사용하면, 불량 동전이 든 주머니를 찾을 수 있을까?
위 문제를 처음 들었을 때, 나는 동전 주머니를 절반씩 나눠가면서 그룹을 지어 나누어 잰 후, 무게가 다른 주머니를 찾아가는 방식으로 생각을 했다. 그래서 최소 2번 / 최악 3번이라고 판단을 했었다.
하지만 주머니에 숫자를 매겨, 첫번째 주머니에서 동전 1개, 두번째 주머니에서 동전 2개..., 다섯 번째 주머니에서 동전 5개를 꺼낸 후, 꺼낸 동전의 전체를 무게를 재어 늘어난 무게만큼의 주머니 번호가 불량 동전이 들어있는 주머니인 것을 예측할 수 있다. 그래서 결론은 1번만 저울을 사용하면 불량 동전이 든 주머니를 확인할 수 있다.
즉, 무게가 151g 이면 1 번 주머니가 답입니다.
무게가 152g 이면 2 번 주머니가 답입니다.
무게가 153g 이면 3 번 주머니가 답입니다.
무게가 154g 이면 4 번 주머니가 답입니다.
무게가 155g 이면 5 번 주머니가 답입니다.
이와 같은 데이터 처리방법을 인덱싱(indexing)라고 한다.
🗄️ 인덱스(index)
📌 인덱스(index)란?
데이터베이스 분야에 있어서 테이블에 대한 동작의 속도를 높여주는 자료 구조를 일컫는다. 인덱스는 테이블 내의 1개의 컬럼, 혹은 여러 개의 컬럼을 이용하여 생성될 수 있다. 고속의 검색 동작뿐만 아니라 레코드 접근과 관련 효율적인 순서 매김 동작에 대한 기초를 제공한다. 인덱스를 저장하는 데 필요한 디스크 공간은 보통 테이블을 저장하는 데 필요한 디스크 공간보다 작다. 그리고 인덱스는 고유 제약 조건을 실현하기 위해서도 사용된다. 고유 인덱스는 중복된 항목이 등록되는 것을 금지하기 때문에 인덱스의 대상인 테이블에서 고유성이 보장된다.
출처: 위키백과
한 마디로 인덱스는,
- 테이블에 대한 검색의 속도를 높여주는 자료 구조입니다.
- 색인이고 메모리 영역의 일종의 목차를 생성하는 개념입니다.
- 따라서, 이런 목차를 이용하여 검색 범위를 줄여 속도를 높일 수 있습니다.
📌 인덱스를 왜 사용하나요?
- 인덱스 테이블은 데이터들이 정렬되어 저장되어 있기 때문에, 해당 조건(
WHERE)에 맞는 데이터들을 빠르게 찾아낼 수 있습니다. - 인덱스를 사용하면
ORDER BY에 의한 정렬(Sort) 과정을 피할 수가 있습니다. search-key가 정렬되어 있기 때문에 조건 검색 시 속도가 빠릅니다.
📌 인덱스의 장점과 단점
👍 장점
- 테이블을 조회하는 속도를 향상할 수 있다.
- 시스템의 전반적인 부하를 줄일 수 있다.
👎 단점
- 인덱스를 관리하기 위해 DB에 추가적인 저장공간이 필요하게 된다.
- 인덱스를 관리하기 위해 추가 작업이 필요하다.
- 인덱스를 잘못 사용하면 오히려 성능이 저하될 수 있다.
📌 인덱스의 종류
- B(Balanced)-tree Index
- Bitmap Index
- IOT Index
- Clustered Index
위와 같이 존재하며 주로 B-tree 구조로 사용된다고 합니다!
📌 인덱스가 어떻게 동작하나요? (B-Tree)
인덱스에는 여러 가지 유형이 있지만 그중에서도 가장 많이 사용하는 인덱스의 구조는 밸런스드 트리 인덱스 구조입니다. 그리고 B TREE 인덱스 중에서도 가장 많이 사용하는 것은 B * TREE와 B + TREE 구조가 가장 많이 사용되는 인덱스의 구조입니다.
B * Tree 인덱스는 대부분의 DBMS 그리고 오라클에서 특히 중점적으로 사용하고 있는 가장 보편적인 인덱스이다. 구조는 위와 같이 Root(기준) / Branch(중간) / Leaf(말단) Node로 구성되며 계층적 구조를 갖고 있다. 특정 컬럼에 인덱스를 생성하는 순간 컬럼의 값들을 정렬하는데, 오라클 서버에서 풀 스캔보다 인덱스 스캔이 유리하다고 판단되었을 때 생성된 인덱스의 정렬한 순서가 중간쯤 되는 데이터를 뿌리에 해당하는 ROOT 블록으로 지정하고 ROOT 블록을 기준으로 가지가 되는 BRANCH 블록을 정의하며 마지막으로 잎에 해당하는 LEAF 블록에 인덱스의 키가 되는 데이터와 데이터의 물리적 주소 정보인 ROWID를 저장합니다.
- 참고)
ROOT에는BRANCH블럭의 시작점에 대한 정보를 갖고 있어 찾고자 하는 데이터의 위치가 어느BRANCH에 위치하는지 알 수 있습니다.BRANCH블럭에서도 마찬가지로LEAF블럭에 대한 시작점 정보를 갖고 있어 어느LEAF에 포함되어 있는지 알 수 있습니다.
