[기본 키] = [기본 키 값] O (1)을 선택 하시겠습니까?

일반적인 현대 RDBMS에서 특정 기본 키를 쿼리하는 것이 키를 사용하여 해시 테이블을 쿼리하는 것만큼 빠르다는 것이 맞습니까?[기본 키] = [기본 키 값] O (1)을 선택 하시겠습니까?

테이블을 탐색하고 기본 키 값을 추적하기 위해 수행되는 "실제 작업"이 있습니까? 기본 키에 대한 자동 인덱스가 있더라도 그것은 생각지도 못한 낭비입니다.

2013-03-31 S. Valmont

빠르지 만 O (1) 일 필요는 없습니다. 많은 데이터베이스 인덱스는 해시 테이블이 아닌 트리 구조입니다. – Barmar

기본 키에 자동 색인을 사용하여 트리 검색을하는 것처럼 들리는군요. O (log n)이 될 것입니다. 어느 것이 실망 스러울 지. 개인적인 것은 없지만 네가 틀렸으면 좋겠다. –

[chapter 19] (http://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CC8QFjAA&url=http%3A%2F%2Fwww.aabu.edu)을 읽으십시오. .jo % 2Ftool % 2Fcourse_file % 2Flec_notes % 2F901331_Fundamentals_of_Database_Systems % 2C_6th_Edition_ % 280136086209% 29.pdf 및 EI = Lj9ZUaHoEIjmrAeHn4C4CQ 및 USG = AFQjCNGr81mTvpcjSnSPei0hWXIAsJCOfQ 및 BVM = bv.44442042, d.bmk)에 대한 질의 처리 알고리즘 최적화 –

데이터베이스 작업에는 보조 메모리 장치 (디스크)에 대한 액세스가 필요합니다. 효율성을 높이려면 블록 액세스 시간 (작업이 아님)을 줄이는 것이 중요합니다. Select 질의의 복잡성은 어떤 종류의 최적화가 이루어 졌는지에 달려 있습니다.
키 속성에 =을 언급 했으므로 파일을 정렬 한 키 특성에 대한 동일성 비교 (primary index)를 사용하면 이진 검색이 효율적입니다. (더 효율적인 다음 내부 검색)가 사용됩니다. 이진 검색은 일반적으로 액세스 로그 (Br) 블록입니다. 여기서 Br은 파일을 차단하는 번호입니다. (이것은 계산을 위해 인덱스를 위해 여분의 블록에 액세스해야 할 수도 있습니다).

또한 인덱스 구현의 유형에 따라 다릅니다. 멀티 레벨 또는 B, B ⁺을 통해 구현 된 경우 액세스 시간은 노드의 키 수에 따라 (블록에 수용 할 수있는 레코드 수에 따라 다름) 더욱 감소 할 수 있습니다.

경험적 유형의 최적화에서 일반적으로 DBMS 시스템은 테이블 카탈로그에 MAX, MIN, AVG 및 다른 종류의 정보를 저장합니다. 따라서 정보가 카탈로그 정보 쿼리 실행 시간에서 파생 될 수 있다면 상수 O (1) 일 수 있습니다.

읽기 : 제 19 장 Algorithms for Query Processing and Optimization

출처

2013-03-31 09:13:52

실제로 데이터베이스 액세스 구조, 저장소 구조 및 쿼리 최적화를 읽은 후에 대답 할 수 있습니다. –

는 이제 InnoDB 스토리지 엔진을 보자. 모든 InnoDB 인덱스는 B- 트리입니다. B- 트리에서 최악의 검색 복잡도는 O (log n)입니다. 그러나 테이블이 거의 전체적으로 메인 메모리에 들어가면 InnoDB는 해시 인덱스를 자동으로 생성 할 수 있습니다. Adaptive Hash Indexes

출처

2013-03-31 09:18:53

[기본 키] = [기본 키 값] O (1)을 선택 하시겠습니까?

답변

관련 문제