두 개 이상의 열에 있는 B-tree 인덱스는 어떻게 생겼습니까?

두 개 이상의 열에 있는 B-tree 인덱스는 어떻게 생겼습니까?

그래서 인덱스와 그 구현에 대해 읽다가 우연히 b-tree 인덱스에 대한 간단한 설명이 있는 웹사이트를 발견했습니다.

http://20bits.com/articles/interview-questions-database-indexes/

b-tree 인덱스는 단일 열에만 있는 인덱스에 매우 적합합니다. 그러나 여러 열이 있는 인덱스를 만든다고 가정해 보겠습니다. 그러면 b-tree는 어떻게 작동합니까?b-tree 내의 각 노드의 값은 얼마입니까?

예를 들어 다음과 같은 표가 있는 경우:

table customer:
id    number
name   varchar
phone_number   varchar
city   varchar

다음으로 인덱스를 만듭니다(id, name, city).

다음 쿼리를 실행합니다.

SELECT id, name 
  FROM customer
 WHERE city = 'My City';

이 쿼리는 다중 열 인덱스를 어떻게 활용합니까? 아니면 인덱스가 (시, ID, 이름) 또는 (시, 이름, ID)로 생성되지 않는 한 활용하지 않습니까?

대부분의 구현에서 키는 단순히 모든 키 값을 포함하는 긴 키와 구분 기호입니다.마법은 없다;-)

이 예에서 키 값은 다음과 같습니다.

"123499|신원미상|콘웨이, NH"32144|빌 게이츠|시애틀

복합 키를 사용하는 이러한 인덱스의 특징 중 하나는 중간 트리 노드를 사용하여 쿼리를 "커버"할 수 있다는 것입니다.

예를 들어, ID가 인덱스에 처음 있기 때문에 ID가 지정된 이름과 도시를 찾는 조회가 있을 경우 인덱스는 이를 기준으로 효율적으로 검색할 수 있습니다.중간 노드에 들어가면 키에서 이름과 도시를 "파싱"할 수 있으므로 리프 노드로 이동하여 읽을 필요가 없습니다.

단, 쿼리에서 전화번호도 표시할 경우 완전한 레코드가 발견되면 로직은 리프 아래로 이동합니다.

가 Python 에는 Python의 비교(col1, col2, col3)가 됩니다.인덱스 처리에는 비교가 포함됩니다.tuple_atuple_b이 있는지 수 관심이 있는 ("인덱스 스캔")를 읽어야 효율이 . 관심 있는 col1과 col2의 값을 알 수 없지만 col3만 알 수 있는 경우 전체 인덱스("전체 인덱스 스캔")를 읽어야 하므로 효율성이 떨어집니다.

인덱스가 (col1, col2, col3)에 있는 경우 WHERE 절에 col1 및 col2(3)의 3열 모두에 대한 참조가 포함되어 있는 경우 RDBMS는 인덱스를 (직접) 사용할 것으로 예상할 수 있습니다.

그렇지 않은 경우(예: WHERE 절의 col3만 해당), RDBMS는 해당 인덱스를 전혀 사용하지 않거나(예: SQLite), 전체 인덱스 스캔(예: Oracle)을 수행합니다(다른 인덱스가 없는 경우).

구체적인 예에서는 ID가 고객의 고유 식별자라고 가정하고 인덱스에 ID를 표시하는 것은 의미가 없습니다(DBMS가 프라이머리 키 또는 UNIQUITY로 기재된 컬럼에 대해 설정해야 하는 인덱스 제외).

일부 구현에서는 단순히 열 순서대로 값을 구분 기호로 연결합니다.

또 다른 해결책은 단순히 b-tree 안에 b-tree를 두는 것입니다.첫 번째 열의 리프를 누르면 일치하는 레코드 목록과 다음 열의 미니 B-트리가 모두 표시됩니다.따라서 인덱스에 지정된 열의 순서에 따라 해당 인덱스가 특정 쿼리에 유용한지 여부가 크게 달라집니다.

지난주에 제가 쓴 관련 질문입니다.

복합 클러스터 인덱스를 사용할 때 SQL Server 점프 리프가 발생합니까?

"인덱스는 첫 번째 키 요소로 정렬되며, 두 번째 키 요소로 정렬됩니다." https://www.qwertee.io/blog/postgresql-b-tree-index-explained-part-1/

Oracle에서는 선행 열이 필터링되지 않더라도 복합 키 인덱스를 사용할 수 있습니다.이것은, 다음의 3개의 메카니즘에 의해서 행해집니다.

1. 전체 인덱스 세그먼트를 이동하는 데 다중 잠금 읽기가 사용되는 빠른 전체 인덱스 스캔입니다.
2. 인덱스가 블록의 논리 순서로 읽히는 인덱스 풀 스캔(최근 버전에서는 Oracle이 멀티 잠금 읽기를 사용할 수 있다고 읽었지만 실제로는 단일 블록 읽기에 의존해야 합니다)
3. Inddex 건너뛰기 스캔을 사용하면 사전 복제되지 않은 선행 열의 카디널리티가 매우 낮기 때문에 Oracle은 선행 열의 고유한 값마다 하나씩 여러 인덱스 범위 스캔을 수행할 수 있습니다.제 경험상 이런 경우는 거의 없습니다.

Oracle 인덱스 내부 정보에 대한 자세한 내용은 Richard Foote 또는 Jonathan Lewis의 기사를 참조하십시오.

에 '복합키' 은 '복합키'입니다.kdtree하지만 각 레벨을 할 때 합니다.k치수를 지정합니다.즉, 트리의 첫 번째 레벨은 첫 번째 치수를 두 부분으로 나누고, 두 번째 레벨은 두 번째 치수를 분할합니다.k+1레벨은 첫 번째 치수를 다시 분할하는 등이것에 의해, 임의의 차원으로 데이터를 효율적으로 분할할 수 있습니다.이 접근법은 "공간" 데이터베이스(예: Oracle Spatial, PostGIS 등)에서는 일반적이지만 "일반" 다중 인덱스 테이블에서는 그다지 유용하지 않을 수 있습니다.

http://en.wikipedia.org/wiki/Kd-tree

(id,name,city) 인덱스를 사용하여 "City = ?" 술어를 충족할 수 있지만 매우 비효율적입니다.

이 쿼리를 만족시키기 위해 인덱스를 사용하려면 원하는 도시가 있는 항목을 찾기 위해 트리 구조의 대부분을 걸어야 합니다.이것은 테이블을 스캔하는 것보다 더 빠른 매그너튜드 순서일 것입니다!

(city, name, id) 인덱스는 쿼리에 가장 적합한 인덱스입니다.원하는 도시 항목을 모두 쉽게 찾을 수 있으며 ID 및 이름 값을 얻기 위해 기본 테이블에 액세스할 필요가 없습니다.

언급URL : https://stackoverflow.com/questions/1648217/what-does-a-b-tree-index-on-more-than-1-column-look-like