MySQL B+tree와 비교하여 btree 인덱스의 포스트그레스 사용

MySQL B+tree와 비교하여 btree 인덱스의 포스트그레스 사용

MySQL에서 PGSQL로 마이그레이션을 진행 중이며 1억 개의 행 테이블을 보유하고 있습니다.

두 시스템 모두 공간을 얼마나 사용하는지 확인하려고 했을 때 테이블의 차이는 훨씬 적었지만 인덱스의 차이는 매우 컸습니다.

MySQL 인덱스는 테이블 데이터 자체보다 더 많은 크기를 차지하고 있었고 포스트그레스는 훨씬 더 적은 크기를 사용하고 있었습니다.

• 그 이유로 파보니 MySQL은 B+ 트리를 사용하여 인덱스를 저장하고 포스트그레스는 B-트리를 사용합니다.

• 인덱스의 내 SQL 사용량은 약간 달랐습니다. 인덱스와 함께 데이터를 저장하지만(크기가 증가했기 때문에) 포스트그레스는 그렇지 않습니다.

이제 질문:

• 데이터베이스 스피크에서 B-트리와 B+트리를 비교해보면 범위 쿼리 O(m) + O(logN) - 범위의 m과 lookup이 B+트리에서 로그인 경우에 더 좋으므로 B+트리를 사용하는 것이 좋습니다.

  이제 B-tree에서는 데이터 노드에 대한 연결된 목록 기반 구조가 없기 때문에 범위 쿼리에 대한 조회가 로그입니다.그런데 포스트그레스는 왜 B-tree를 사용합니까?범위 쿼리에 대해 성능이 우수합니까(그렇지만 B-tree로 내부적으로 어떻게 처리합니까?)

• 위 질문은 포스트그레스 관점이지만 MySQL 관점에서 포스트그레스보다 스토리지를 더 많이 사용하는 이유는 무엇인가요, 실제로 B+트리를 사용할 경우 성능상 이점은 무엇인가요?

제가 많은 부분을 놓쳤거나 오해할 수도 있었으니, 부디 여기서 제 이해를 수정해 주시기 바랍니다.

Rick James 질문에 답변하기 위해 편집

• MySQL에 InnoDB 엔진을 사용하고 있습니다.
• 데이터를 채운 후 인덱스를 만들었습니다 - 포스트그레스에서 했던 것과 동일한 방식으로.
• 인덱스가 UNIQUE 인덱스가 아니라 일반 인덱스일 뿐입니다.
• 무작위 삽입은 없었고, 포스트그레스와 MySQL 모두 csv 로딩을 사용했고, 이후에야 인덱스를 만들었습니다.
• 인덱스와 데이터 모두 포스트그레스 블록 크기가 8KB입니다. MySQL은 잘 모르겠지만 변경하지 않았기 때문에 기본값이어야 합니다.
• 행을 크게 부르지 않습니다. 길이 200자의 텍스트 필드가 4개, 소수점 필드가 4개, 비긴트 필드가 2개입니다. 19개의 숫자가 있습니다.
• P.K는 19개의 숫자로 된 큰 칸인데 부피가 큰지 모르겠네요?부피가 큰 것과 그렇지 않은 것을 어떤 규모로 구별해야 합니까?
• MySQL 테이블 크기는 600MB였으며 Postgres는 인덱스를 포함하여 약 310MB였습니다. 이는 제 수학이 맞다면 48% 더 큰 크기입니다.그런데 MySQL에서 테이블 사이즈를 제외하고 인덱스 사이즈만 측정할 수 있는 방법이 있을까요?그게 더 좋은 숫자로 이어질 수 있을 것 같아요.
• 기계 정보 : 모든 테이블과 인덱스를 맞추기에 충분한 RAM - 256GB를 가지고 있었지만, 이 경로를 통과할 필요는 전혀 없다고 생각합니다. 두 가지 모두에서 뚜렷한 성능 차이를 볼 수 없었습니다.

추가 질문

• 파편화가 발생한다고 말할 때?이것을 넘어서는 아무것도 할 수 없다고 말할 수 있도록 탈파편화를 할 수 있는 방법이 있을까요?그런데 저는 센트 OS를 사용하고 있습니다.
• MySQL에서 기본 키가 클러스터될 때 무시하고 인덱스 크기를 측정하여 실제로 어떤 유형이 더 큰 크기를 차지하는지 확인할 수 있는 방법이 있습니까?

먼저 InnoDB를 사용하지 않는 경우 이 질문을 닫고 InnoDB로 재구축한 다음 질문을 다시 열어야 하는지 확인합니다.내 ISAM은 선호되지 않으므로 논의해서는 안 됩니다.

MySQL에서 인덱스를 어떻게 구축했습니까?인덱스를 명시적으로 또는 암묵적으로 구축하는 몇 가지 방법이 있습니다. 이는 더 나은 패킹 또는 더 나쁜 패킹으로 이어집니다.

MySQL: Data와 Index는 16KB 블록으로 구성된 B+Tree에 저장됩니다.

MySQL:UNIQUE함) )PRIMARY KEY행을 삽입할 때 업데이트해야 합니다.비상대기상태UNIQUE인덱스는 반드시 많은 블록 분할 등을 가질 것입니다.

MySQL: 는 데이터와 함께 클러스터링되어 있어 사실상 공간을 전혀 차지하지 않습니다.데이터를 PK 순서로 로드하면 블록 조각화가 최소화됩니다.

-UNIQUE보조 키는 즉시 구축될 수 있으며, 이로 인해 파편화가 발생할 수 있습니다.또는 테이블이 로드된 후에 구성할 수도 있습니다. 이렇게 하면 패킹 밀도가 높아집니다.

()UNIQUE또는 그렇지 않음)을 암시적으로 포함합니다.PRIMARY KEY그들 안에 경우 .PK가 "큰"인 경우 보조 키의 부피가 큽니다.당신의 PK는 무엇입니까?이것이 '답'입니까?

이론적으로 BT트리에 완전 무작위 삽입하면 블록이 약 69% 가득 차게 됩니다.아마 이것이 답일 것입니다.MySQL이 45%(1/69%) 더 커집니까?

100M 행의 경우 필요한 모든 데이터 및/또는 인덱스 블록을 캐싱하기에 충분한 RAM이 없기 때문에 많은 작업이 I/O 바인딩됩니다.만약 모든 것이 캐시된다면, B-Tree와 B+Tree는 큰 차이가 없을 것입니다.캐시가 완료되지 않았을 때 범위 쿼리에 대해 수행해야 할 작업을 분석해 보겠습니다.

두 가지 유형 중 하나의 트리에서 작업은 트리의 드릴다운으로 시작됩니다.MySQL의 경우 100M 행에는 약 4단계 깊이의 B+Tree가 있습니다.리프가 아닌 노드 3개(또 다시 16KB 블록)는 캐시되고(아직 없는 경우) 재사용됩니다.Postgres의 경우에도 이 캐싱이 발생할 수 있습니다. (나는 Postgres를 모릅니다.)그런 다음 범위 스캔이 시작됩니다.MySQL을 사용하면 블록의 나머지 부분을 걷게 됩니다. (Rule of Thumb: 한 블록의 100 행)포스트그레스를 위한 Ditto?

블록의 끝에서 뭔가 다른 일이 일어나야 합니다.MySQL의 경우 다음 블록으로 연결되는 링크가 있습니다.해당 블록(100개의 행이 더 있음)은 캐시되지 않은 경우 디스크에서 가져옵니다.B-Tree의 경우 리프가 아닌 노드를 다시 통과해야 합니다. 2, 아마도 3개의 레벨이 여전히 캐시됩니다.디스크에서 1/10K 행만 가져올 다른 비리프 노드가 필요합니다.(10K = 100*100) 즉, "콜드" 시스템에서도 Postgres가 MySQL보다 1% 더 자주 Disk에 도달할 수 있습니다.

반면 열이 16K 블록에 1개나 2개만 들어갈 정도로 살이 찐다면 계속 사용하던 '100'은 '2'에 가까우며 1%는 50%가 될 수도 있습니다.즉, 큰 행이 있으면 이것이 "정답"이 될 수 있습니다.그런가요?

포스트그레스의 블록 사이즈는 어떻게 됩니까?위의 많은 계산은 블록과 데이터 사이의 상대적인 크기에 의존합니다.이것이 답이 될 수 있을까요?

결론:가능한 4가지 답변을 드렸습니다.질문을 확대하여 이들 각각이 해당되는지 확인하거나 반박하시겠습니까? (2차 인덱스 존재, 큰 PK, 2차 인덱스의 비효율적인 구축, 큰 행, 블록 크기 등)

기본 키에 대한 추가 사항

InnoDB의 경우, 또 하나 주목해야 할 사항은...가 있는 것이 가장 좋습니다.PRIMARY KEY데이터를 로드하기 전에 표의 정의를 참조합니다.를 PK다 .LOAD DATA. 지정하지 않고PRIMARY KEY아니면UNIQUEkey, InnoDB는 숨겨진 6바이트 PK를 구축합니다. 이는 일반적으로 차선입니다.

데이터베이스에서는 ID와 같은 100에서 200 사이의 데이터 범위를 제공하는 사용자를 자주 쿼리합니다.
이경우

• B-Tree는 데이터 포인터를 가져오려면 모든 항목에 대해 루트에서 리프까지의 경로를 따라야 합니다.
• B+-나무는 잎 사이를 '걸어' 갈 수 있으며 잎으로 가는 경로를 처음만 따라야 합니다(즉, ID 100의 경우).

이는 B+-Tree가 리프에 데이터(또는 데이터 포인터)만 저장하고 리프가 연결되어 신속한 순서 이동을 수행할 수 있기 때문입니다.

B+트리

또 다른 점은 다음과 같습니다.
B+Tree에서는 내부 노드가 데이터 포인터 없이 다른 노드에 대한 포인터만 저장하기 때문에 포인터를 위한 공간이 늘어나고 IO-Operations가 적게 필요하며 메모리 페이지에 노드 포인터를 더 많이 저장할 수 있습니다.

따라서 범위 쿼리 B+ 트리가 최적의 데이터 구조입니다.단일 선택의 경우(트리의 깊이/크기 원인) 데이터 포인터가 트리 내부에 위치하기 때문에 B-트리가 더 나을 수 있습니다.

MySQL 및 PostgreSQL은 여기서 실제로 비교할 수 없습니다. Innodb는 인덱스를 사용하여 테이블 데이터를 저장합니다(그리고 보조 인덱스는 바로 pkey를 가리킵니다).이것은 단일 행 pkey 검색과 B+ 트리의 경우 pkey 필드에 대한 범위 쿼리를 수행하는 데 유용하지만, 다른 모든 것에 성능상의 단점이 있습니다.

PostgreSQL은 힙 테이블을 사용하고 인덱스를 별도로 둡니다.다양한 인덱싱 알고리즘을 지원합니다.범위 쿼리에 따라 bt트리 인덱스가 도움이 되지 않을 수 있으며 대신 GiST 인덱스가 필요할 수 있습니다.마찬가지로 GIN 인덱스는 멤버 룩업(어레이, ft 등)과 잘 작동합니다.

btree는 단순한 사용 사례가 뛰어나기 때문에 사용하는 것 같습니다. 어떤 roes에 다음과 같은 데이터가 포함되어 있습니까?예를 들어, 이것은 GIN의 빌딩 블록이 됩니다.

하지만 포스트그레는 사실이 아닙니다.SQL은 B+ 트리를 사용할 수 없습니다.GiST는 일반화된 형식으로 B+ Tree 인덱스를 기반으로 합니다.소 포스트그레SQL은 B+ 트리를 편리한 곳에서 사용할 수 있는 옵션을 제공합니다.

언급URL : https://stackoverflow.com/questions/33009174/postgres-usage-of-btree-indexes-vs-mysql-btrees