index, Tree

유튜브 코딩애플의 index 영상을 보고 정리한거

 

 

순서대로 정렬해놔야 절반씩 소거하며 찾기 가능

ex) 1 ~ 100 중 50보다 작냐?  25보다 크냐?  이런식

 

index

컬럼을 복사해서 정렬해둔 개념

실제로 Tree 형태로 구현됨

 

 

Tree

왼쪽은 이전꺼, 오른쪽은 다음꺼

Binary Search Tree라고도 함( 2의 거듭제곱 )

 

B-Tree는 2번이동으로 1 ~13 검색 가능

 

 

B+tree는 맨아래 노드끼리 화살표로 연결되있음

범위 검색이 쉬움

ex) 4 ~ 8 어딨음?  >>   4찾고 화살표 타고 다음노드로 이동만 하면 끝