---------------------------------------------
Markus Winand는 SQL에 대한 통찰력을 제공하고 다양한 시스템이 SQL을 지원하는 방법을 modern-sql.com 에서 보여줍니다. 이전에 그는 use-the-index-luke.com 을 만들었는데, 지금도 활발하게 유지되고 있습니다. Markus는 winand.at 를 통해 강사, 연사 및 컨설턴트로 고용될 수 있습니다.
---------------------------------------------
You can upload a Korean translation of use-the-index-luke.com on your blog
Thank you from the bottom of my heart to author Makus Winand for allowing me.
These are translations that I use for studying by using a papago (google translate)
The translations may not be correct or there may be a typo.
I'd appreciate it if you could point it out in the comments.
---------------------------------------------
---------------------------------------------
use-the-index-luke.com 의 한글번역본을 블로그에 업로드 해도 된다고
허락해주신 Makus Winand 님께 진심으로 감사합니다.
이 번역본들은 제가 공부용도로 번역기(papago, google transrate)를 돌려서
번역한 내용들이라 맞지 않거나, 오타가 있을수 있습니다.
댓글로 지적해주시면 감사하겠습니다.
---------------------------------------------
검색 트리(B-Tree)를 통해 인덱스가 고속화되다
https://use-the-index-luke.com/sql/anatomy/the-tree
인덱스 리프노드는 임의의 순서로 저장됩니다. 디스크상의 위치는 인덱스순서에 따른 논리위치와 일치하지 않습니다. 그것은 페이지가 뒤섞인 전화번호부 같다. "Smith"를 검색하지만 "Robinson"에서 먼저 디렉토리를 열면 스미스가 Robinson을 따라가는 것은 결코 허용되지 않습니다. 데이터베이스에는 쉐이핑된 페이지 중 엔트리를 신속하게 찾기 위한 두 번째 구조, 즉 균형 잡힌 검색 트리, 즉 B-트리가 필요합니다.
그림 1.2 B-Tree 구조
그림 1.2는 30개의 엔트리가 있는 인덱스의 예를 나타내고 있습니다. 이중링크 목록은 리프 노드간의 노리적 순서를 설정합니다. 루트 노드 및 브랜치노드는 리프 노드간의 빠른 검색을 지원합니다.
이 그림에서는 분기 노드와 해당 노드가 참조하는 리프 노드가 강조 표시되어 있습니다.
각 분기 노드 엔트리는 각 리프 노드에서 가장 큰 값에 대응합니다.
첫 번째 리프 노드를 예로 들어 보겠습니다.
이 노드에서 가장 큰 값은 46입니다. 이 값은 대응하는 브랜치노드 엔트리에 저장됩니다.
다른 리프노드도 마친가지이므로 최종적으로 브랜치노드는 값 46, 53, 57 및 83을 가집니다. 이 schema에 따르면 모든 리프 노드가 브랜치노드로 커버될 때까지 브랜치층이 구축된다.
다음 계층은 마찬가지로 첫 번째 지점 노드 수준위에 구축됩니다. 모든 키가 단일(루트 노드)에 들어갈때 까지 이 절차를 반복합니다. 트리의 깊이가 모든 위치에서 동일하기 때문에 이 구조는 균형 잡힌 검색트리이며 루트 노드와 리프 노드 간의 거리는 어디에서나 동일합니다.
작성되면 데이터베이스는 index를 자동으로 유지합니다. 모든 경우에 해당됩니다.
insert, delete 그리고 update는 인덱스로 이행하여 트리의 균형을 유지하여 쓰기 작업의 유지보수 오버헤드를 발생시킵니다.
8장 "데이터 수정"에서는 이에 대해 자세히 설명합니다.
그림 1.3 B-Tree Traversal(순회)
그림 1.3은 키 "57"의 검색을 설명하기 위한 인덱스 조각입니다. Tree Traversal(순회)은 좌측 루트노드에서 시작합니다. 각 엔트리는 검색어(57) 이상의 값이 될 때까지 오름차순으로 처리된다. 그림에서 그것은 엔트리 83이다. 데이터베이스는 대응하는 분기 노드에 대한 참조를 따르며 Tree Traversal이 리프 노드에 도달할때까지 이 절차를 반복합니다.
--------------------------------------------
Important
B-tree를 사용하면 데이터베이스는 리프 노드를 빠르게 검색할 수 있습니다.
--------------------------------------------
Tree travelsal은 매우 효율적인 작업입니다.
매우 효율적이기 때문에 인덱싱의 제 1의 힘이라고 할 수 있습니다.
대규모 데이터 세트에서도 거의 즉시 작동합니다. 이는 주로 동일한 수의 스템으로 모든 요소에 액세스할 수 있는 트리 밸런스 때문이며, 두 번쨰는 트리 깊이의 로그 성장 때문입니다. 즉, 나뭇잎 노드의 수에 비해 나무의 깊이가 매우 느리게 성장한다는 것을 의미합니다. 수백만 개의 기록이 있는 실제 세계 인덱스는 트리 깊이가 4, 5개 입니다.
Tree의 깊이가 6인 경우는 거의 볼 수 없다.
Logmatic scalability 에서 이 내용을 설명하고 있습니다.
Logmatic scalability
--------------------------------------------
수학에서, 주어진 기수에 대한 숫자의 로그는 숫자를 생성하기 위해 기수를 올려야 하는 거듭제곱 또는 지수입니다.
검색트리에서 베이스는 분기 노드당 엔트리 수에 대응하고 지수는 트리 깊이에 대응합니다. 그림 1.2의 예저 인덱스는 노드당 최대 4개의 엔트리를 보유하고 있으며 트리 깊이는 개 입니다. 즉, 인덱스는 최대 64개(4의 3제곱)의 엔트리를 유지할 수 있습니다.
1레벨 증가 시 이미 256엔트리(4의 4제곱)를 유지할 수 있습니다. 로그는 이 함수를 반전시킵니다. 따라서 트리의 깊이는
log 4(Index -entry 갯수)
입니다.
로그 증가는 예저 인덱스가 10개의 트리 레벨로 백만개의 레코드를 검색할 수 있게 하지만 실제 인덱스는 휠씬 더 효율적 입니다.
트리 깊이, 즉 검색성능에 영향을 주는 주요 요인은 각 트리 노드의 엔트리 수입니다.
이 숫자는 수학적으로 logarithm(log)의 기초에 해당합니다. 기초가 높을수록 나무가 얕아질수록 횡단 속도가 빨라집니다.
데이터베이스는 이 개념을 최대한 활용하여 각 노드에 가능한 많은 항목(대부분 수백 개)을 추가합니다. 즉, 새로운 인덱스레벨마다 100배 이상의 엔트리가 지원됩니다.
--------------------------------------------
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
ㄴ Btree 시뮬레이터
'use-the-index-luke' 카테고리의 다른 글
| 2장 WHERE 문 (0) | 2023.06.15 |
|---|---|
| 1.3 Slow Indexes, Part I (0) | 2023.06.13 |
| 1.1 The Index Leaf Nodes (0) | 2023.06.05 |
| 1장 인덱스의 구조 (0) | 2023.06.02 |
| SQL Indexing and Tuning e-Book && 저자소개 및 감사 인사 (0) | 2023.06.02 |
