# Index 개념 정리

<figure><img src="https://3814826491-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJyHOwztPxBT3bLpisjCt%2Fuploads%2F6iULwZjszo10dQjsk7i1%2FScreenshot_59.png?alt=media&#x26;token=45e19f6f-6deb-4eac-ba0c-2e24958449ac" alt=""><figcaption></figcaption></figure>

\
테이블 안에 데이터가 1억개 있는데 거기서 'age' 컬럼이 20인 사람을 찾고 싶으면 어쩌죠?&#x20;

SELECT 명령을 내리면 되는데 그럼 컴퓨터는 1억개의 행을 다 뒤져봐야합니다. (매우느림)

그게 싫으면 index를 만들어두면 됩니다.&#x20;

&#x20;



<figure><img src="https://3814826491-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJyHOwztPxBT3bLpisjCt%2Fuploads%2F1agWaRyaYQgpsqWvRcRF%2Findex_example.jpg?alt=media&#x26;token=d222c572-73ec-485c-8ff5-645c1e299be2" alt=""><figcaption></figcaption></figure>

Index는 사전에 맨뒤에 있는거라고 생각하면 쉬운데

요즘은 실물사전을 모르는 사람도 많을테니

게임을 하나 해보겠습니다.



### **업다운놀이**

<figure><img src="https://3814826491-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJyHOwztPxBT3bLpisjCt%2Fuploads%2F8M2hdqyW1TKDRFTfng35%2FScreenshot_60.png?alt=media&#x26;token=e5098a67-7b70-43c1-ad32-ae9dff4c0244" alt=""><figcaption></figcaption></figure>

&#x20;1부터 100까지 써있는 카드를 책상에 진열해놨습니다.

제가 지금 어떤 숫자를 생각하고 있는지 맞춰보십시오.

저는 "예/아니오" 로만 대답할 수 있습니다. &#x20;



멍청한 사람은&#x20;

1입니까? / 아뇨

2입니까? / 아뇨

3입니까? / 아뇨

이렇게 계속 물어보겠지만

&#x20;

똑똑한 사람은

50보다 큽니까? / 넹

그렇다면 75보다 작습니까? /넹

그럼 68보다 큽니까? / 아뇨

이런 식으로 반을 자르면서 답이 아닌걸 소거합니다.&#x20;

그럼 훨씬 적은 질문으로 답을 찾아낼 수 있으니까요.&#x20;



데이터베이스에 있는 데이터도 그런 식으로 반을 자르면서 검색할 수 있습니다.

그럼 1억개의 행이 있어도 몇십번의 질문 만에 데이터를 찾을 수 있는데

그렇게 하려면 조건이 있습니다.

찾을 컬럼을 123, 혹은 가나다 순으로 정렬해놔야한다는 것입니다. 그래야 절반씩 치우죠

그래서 검색을 빠르게 만들기 위해 "따로 복사 후에 정렬해둔 컬럼"을 index라고 합니다.&#x20;





### **Binary search tree**



<figure><img src="https://3814826491-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJyHOwztPxBT3bLpisjCt%2Fuploads%2FIhwbsxUMvamaG6frhBXC%2FScreenshot_61.png?alt=media&#x26;token=aa95c80d-ce85-4cb1-80b5-eb7f09242a53" alt=""><figcaption></figcaption></figure>

데이터를 빠르게 찾고싶으면 데이터를 미리 정렬해두면 된다고 했습니다.&#x20;

숫자 뿐만 아니라 문자도 마찬가지입니다.&#x20;

그럼 아까처럼 절반씩 치우면서 검색할 수 있으니까요.&#x20;



<figure><img src="https://3814826491-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJyHOwztPxBT3bLpisjCt%2Fuploads%2FEsQKcfDfYngSrYvzU6av%2Fbsttreetraversal.png?alt=media&#x26;token=f9baa3c3-f8c5-4208-8c47-de5c666f96af" alt=""><figcaption></figcaption></figure>

실은 굳이 물리적으로 일렬로 정렬을 안해도&#x20;

1\. 사진처럼 숫자를 왼쪽부터 123 순으로 배치만 잘 하고

2\. 서로 화살표로 이어둬도

아까처럼 반씩 갈라가며 빠르게 검색이 가능합니다.&#x20;



위 사진을 뒤집어놓은 나무같다고 해서 이걸 전문용어로 Binary search tree 라고 부릅니다.&#x20;

그래서 데이터를 Binary tree 형태로 미리 배치해놓아야 빠르게 찾을 수 있다고 이해해도 똑같습니다.&#x20;

실제로 index도 tree 형태로 배치해두는 경우가 많습니다.&#x20;





### **B-tree (비 트리)**



하지만 50%씩 소거하며 찾는 것 말고&#x20;

66% 아니면 75%씩 소거해버리고 그럴 수도 있지 않을까요?&#x20;

B-tree 형태로 자료를 배치해두면 가능합니다.&#x20;



<figure><img src="https://3814826491-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJyHOwztPxBT3bLpisjCt%2Fuploads%2FlmVpOSOwLkNuz3qQQ2PO%2FScreenshot%202023-10-19%20at%2000.22.29.JPG?alt=media&#x26;token=d689af05-e883-46b7-968a-cb2bcb371830" alt=""><figcaption></figcaption></figure>





1\. 하나의 네모칸 안에 숫자를 여러개 담아놓는 식으로 배치하고&#x20;

2\. 갈림길을 3개 이상으로 쪼개놓는 겁니다.&#x20;

이걸 B-tree라고 부릅니다.&#x20;

&#x20;

그럼 훨씬 적은 횟수로 많은 데이터를 찾아낼 수 있겠군요.&#x20;

아까는 2번의 화살표 이동으로 1\~7까지 찾을 수 있었는데

지금은 2번의 화살표 이동으로 1\~13까지는 충분히 찾을 수 있을듯요 &#x20;





### **B+tree (비 플러스 트리)**



하지만 똑똑한 컴퓨터과학자들이 더 나은 방법을 발명해내는데&#x20;

B+tree라고 해서 데이터를 트리 중간중간에 보관하는게 아니라 가장 밑에만 보관하는겁니다.&#x20;



<figure><img src="https://3814826491-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJyHOwztPxBT3bLpisjCt%2Fuploads%2Fw8bUja10i14hU4SlSLJE%2FScreenshot%202023-10-19%20at%2000.24.03.JPG?alt=media&#x26;token=2ab9a16c-419e-42d6-94bc-410fc9f04dc1" alt=""><figcaption></figcaption></figure>





B+tree는 B-tree와 정렬방식이 똑같은데 데이터를 가장 밑에만 저장해두는 것입니다.

가장 밑부분에 테이블을 일정한 크기로 쪼개놓고 순서대로 정렬해둡니다.

그리고 데이터 탐색 가이드라인만 윗부분에 저장해둡니다.&#x20;

&#x20;

이렇게 해둬도 아까랑 똑같이 두세번 만에 데이터를 찾을 수 있는데&#x20;

더 나은 점은 **"나이가 2와 5사이인 행을 다 찾아주세요\~"** 같은 범위검색을 할 때 훨씬 빠르게 찾을 수 있습니다.

&#x20;

왜냐면 B+tree는 내 옆 데이터들도 화살표로 몰래 연결을 해놓는데

화살표 덕분에 내 옆의 테이블 조회까지 매우 쉬워지기 때문입니다.&#x20;

그래서 "나이가 2인 행을 먼저 찾은 다음에 5까지 전부 출력해주세요\~" 그런 명령을 매우 빠르게 수행해줍니다.



그래서 관계형 DB들은 일반적으로 B+tree로 index를 정렬해둡니다.&#x20;

물론 B+tree 안쓰는 데이터베이스들도 있습니다.

&#x20;

&#x20;&#x20;

&#x20;

결론은 그래서 컬럼을 잘라내서 tree 형태로 정렬해둔걸 전문용어로 index라고 하는데&#x20;

실제로 index를 컴퓨터가 어떻게 활용하냐면&#x20;

&#x20;

컴퓨터에게 "WHERE age = 20인 행을 찾아주세요\~" 라고 시키면

1\. 컴퓨터는 index 안에서 age가 20인 행을 빠르게 찾고

2\. age가 20인 index의 행과 연결된 원래 테이블의 행을 찾아와서 결과로 출력해줍니다.&#x20;

그런 과정 덕분에 검색속도가 빨라지는 것입니다.&#x20;

&#x20;

\
\=, >, >=, <, <=, BETWEEN, LIKE 연산자를 사용할 때 index가 사용됩니다.&#x20;

LIKE 사용시엔 시작이 %기호가 아닐 때만 (LIKE 어쩌구% 일 때만) index를 사용해줍니다.&#x20;



**하지만 index는 자동생성되진 않음**&#x20;



여러분이 "이 컬럼의 index를 만들어주세요\~" 라고 요구해야 index 생성이 가능합니다.&#x20;

index는 항상 필요한게 아니니까요&#x20;



**자동으로 index가 적용되는 컬럼이 있음**&#x20;

Primary key 컬럼은 따로 index를 만들 필요가 없습니다.&#x20;

왜냐면 테이블에 Primary key가 있으면 애초에 Primary key 기준으로 정렬해서 보관해줍니다.&#x20;

그래서 그냥 index가 기본으로 생성되어있습니다.&#x20;

&#x20;

그래서 Primary key 검색시엔 별거 안해놔도 매우 빠르게 찾아줍니다.&#x20;

Primary key가 아닌 일반 컬럼들은 검색속도를 향상시키고 싶으면 index를 만들어놔야합니다.&#x20;





### **Index의 단점**



테이블의 컬럼마다 index 만들어두면 SELECT 문법을 매우 빠르게 처리해줄 수 있는데&#x20;

1\. index를 만들 때 마다 추가 하드용량을 차지합니다. (컬럼 한두개 복사하는 수준이라 별문제는 아님)

2\. index가 있는 테이블은 나중에 삽입, 수정, 삭제 문법으로 데이터 넣을 때 내부적으로 추가연산이 필요해 느려질 수 있습니다.

왜냐면 테이블과 index 에 각각 데이터를 반영해야하니까요.

근데 오히려 데이터가 많으면 삽입, 수정, 삭제시에도 원하는 행을 찾는데 매우 빨라져서 크게봤을 때 단점은 아닙니다.  &#x20;

그래서 자주 찾게될 컬럼이 있다면 index를 만들어놓도록 합시다.&#x20;
