728x90 반응형 index2 [DB] 인덱스에서 B tree 를 쓰는 이유 B tree는 BST(Binary Search Tree, 이진 탐색 트리) 보다 확장된 형태입니다. BST는 자식노드가 최대 2개인 트리 왼쪽 서브트리는 부모보다 작은 값, 오른쪽 서브트리는 부모보다 큰 값 B Tree는 이보다 확장되어 자식노드를 2개 이상 가질 수 있는 트리입니다.모든 leaf 노드(최하위 노드)들은 같은 레벨에 있습니다. 최대 자식노드 수 M이 5 일 때 5차 B tree 라고 합니다. 최대 자식 수 M최대 키 수 M-1최소 자식 수 M/2의 올림 (root, leaf node 제외)최소 키 수 M/2의 올림 – 1 (root node 제외) DB 인덱스에 B tree 계열을 사용하는 이유 B tree 계열 (B+ tree, B.. 2024. 3. 20. [DB] 인덱스, unique index, multicolumn index, hash index where name = '홍길동' name 이라는 컬럼에 인덱스 없으면 100만개 full scan – 시간복잡도 O(N) 인덱스가 걸려있고 B-tree 기반이라면 O(logN) 일반 인덱스 : 중복 가능 유니크 인덱스 : 중복 불가능 여러개를 한번에 묶어서 인덱스 생성 가능 = multicolumn index 테이블을 생성하면서 만들 수도 있고 테이블 생성 후에 만들 수도 있음 primary key에는 RDBMS가 자동으로 인덱스를 생성해준다. where a = 7 and b = 95; 위의 경우 a에 대해서 인덱스를 생성하면 인덱스내에서 a = 7인 것을 찾고 또 a = 7인 것들을 full scan해서 b = 95 인 것을 찾아야 하기 때문에 비효율적이다. 그래서 a, b를 하나로 묶은 인덱스를 만.. 2024. 3. 19. 이전 1 다음 728x90 반응형
