데이터베이스 쿼리 시간 복잡도

Question

저는 데이터베이스에 익숙하지 않아 어리석은 질문 인 경우 용서해줍니다.

현대 데이터베이스에서 색인을 사용하여 행에 액세스하면 O (1) 복잡성이 발생합니다. 그러나 다른 열을 선택하기 위해 쿼리를 수행하면 O (1) 또는 O (n)이됩니까? 데이터베이스가 모든 행을 반복해야합니까, 아니면 각 열에 대해 정렬 된 목록을 작성합니까?

Answer 1

실제로 인덱스를 기반으로 한 액세스는 O (log (n))가 될 것입니다. 레코드를 얻기 위해 여전히 B-Tree-esque 조직을 검색 할 것이기 때문입니다.

Answer 2

색인이 있습니다. 클러스터 된 인덱스는 디스크에서 물리적으로 정렬되므로 테이블 당 하나만 가질 수 있습니다. 클러스터되지 않은 인덱스는 논리적으로 정렬되며 많은 인덱스를 포함 할 수 있습니다 (남용하지 않도록주의하십시오. 쓰기 작업 속도가 느려질 수 있습니다). 당신의 칼럼에 색인이 없다면 나는 그것이 행에 의해 좋은 옛날 행법이라고 믿습니다.

Answer 3

인덱스는 열마다 있으므로 인덱스가없는 열에 where 절을 사용하면 테이블 스캔 (O (n))이 수행됩니다.

Answer 4

리터럴 질문에 대답하려면 예, 열에 인덱스가 없으면 데이터베이스 엔진은 모든 행을 살펴야합니다.

인덱스를 사용하거나 사용하지 않는 여러 열에서 선택하는 것이 더 흥미로운 경우에는 상황이 더욱 복잡해집니다. 쿼리 최적화 프로그램이 인덱스를 사용하도록 선택하면 먼저 인덱스를 기반으로 행을 선택한 다음 나머지 제약 조건이있는 필터를 적용하십시오. 따라서 O (행 수)에서 O (인덱스 별 선택된 행 수)까지 두 번째 필터링 연산을 줄입니다. 이 두 숫자의 비율을 선택도이라고하며 사용할 색인을 선택할 때 중요한 통계입니다.

Answer 5

서로 다른 데이터베이스 유형에 따라 인덱스 유형, 실행 계획 및 구현 방식이 다릅니다. 관계 데이터베이스의 코드 대부분은 검색 최적화 알고리즘에 있습니다. 귀하의 질문에 대한 대답은 하나도 없습니다. 도구를 사용하여 쿼리 실행 방법을 알고 싶을 때 실행 계획을 시각화 할 수 있습니다.

Answer 6

답을 모르겠지만 big-O 표기법은 임의로 큰 데이터 세트 크기에 대한 성능 표시 만 제공한다는 점에 유의하십시오.

예를 들어 데이터베이스 성능의 병목 현상은 일반적으로 디스크 검색입니다. 따라서 작업 데이터 집합을 메모리에 보관할 수 있으면 성능이 크게 향상됩니다. Big-O 표기법은 유한 데이터 세트에만 관련이 있으므로 이러한 최적화에 대해 알려주지 않습니다.

Answer 7

B- 트리는 O (logN)을 생성하지 않습니다. 즉, 이진 트리의 복잡성입니다.

B- 트리는 노드 당 전체 블록을 가지도록 구성되어 있으므로 노드가 발견되면 단일 I/O 작업으로 전체 블록을 읽을 수 있습니다.

노드 당 항목 수 = 차단 계수 (# 레코드/블록) {bfr}를 사용하면 B- 트리 최적화 검색은 O (로그 _{bfr ÷ 2 +1} N) 개의 I/O 연산을 생성합니다. O (N) 키로 레코드를 찾는 I/O 작업.