DB11 - Index

Data Structures in DB Internals

• Data structures are used all around DBMSs for many purposesDBMS(데이터베이스 관리 시스템) 전반에서 다양한 목적을 위해 자료구조가 사용된다.

  • Internal meta-data
    내부 메타데이터
    

    • Page tables 페이지 테이블

    • Page directory 페이지 디렉토리

    • Page headers, Tuple headers 페이지 헤더, 튜플 헤더

    • Various page mappings; e.g., page_id to frame, page_id to some allocation on disk (hash tables)다양한 페이지 매칭 (예 : page_id를 메모리 프레임 또는 디스크 내의 특정 할당 영역에 매칭 (해시 테이블 사용))

  • Core data storage (the database itself)
    핵심 데이터 저장 구조 (즉, 데이터베이스 자체)
    

    • Heaps of pages페이지 힙 구조

    • Hash tables, b+tree or other types of trees해시 테이블, B+ 트리 또는 다른 트리 구조

    • Memory cache (a huge hash table)메모리 캐시 (거대한 해시 테이블 형태)

  • Temporary data structures
    임시 자료 구조
    

    • Created and used when executing queries쿼리를 실행할 때 생성되고, 사용된다.

  • Table indexes
    테이블 인덱스
    

    • Building glossary of keys inside of tuples for quick look-ups튜플 내부 키들의 사전을 생성하여 빠른 조회가 가능하도록 함.

• For the first three, hash tables may be enough첫 세 가지 용도에는 해시 테이블만으로도 충분할 수 있다.

  • Hash table: good for point query look-ups (single key look-ups)해시 테이블 : 단일 키 기반의 조회 (포인트 쿼리)에 적합하다.

    • Used in many places in DBMS; e.g.,DBMS 내부 여러 위치에 사용된다.

      • Meta-data메타 데이터 저장

      • Storing n-ary tablesn차 관계 테이블 저장

      • Temporary data structures임시 구조 저장

  • Hash tables cannot serve table indexes well하지만, 해시 테이블은 테이블 인덱스 용도로는 적합하지 않다.

Agenda

• Database indexes 데이터베이스 인덱스

• Ordered indexes 정렬된 인덱스

  • Indexed-sequential files 순차 인덱스 파일

  • B+tree index files B+트리 인덱스 파일

    • B+tree nodes B+트리 노드

    • Queries on B+trees B+트리를 활용한 쿼리 처리

    • B+tree operations B+트리 연산

• Hash indexes (will not cover) 해시 인덱스 (본 자료에서는 다루지 않음)

• Inverted index 역방향 인덱스

Indexes in Books

• At the end of our textbook…우리 교과서의 마지막 부분에서는

  • Complements the table of contents by enabling access to information by specific subject목차를 보완하면서, 특정 주제별로 정보를 접근할 수 있도록 돕는다.

Indexes in Databases

• Indexing mechanisms are to speed up access to desired data인덱스 메커니즘은 원하는 데이터에 더 빠르게 접근하기 위해 사용된다.

  • Improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space추가적인 쓰기 작업과 저장 공간을 희생하면서도, 데이터 조회 속도를 크게 향상시킨다.

  • Replica of a subset of table attributes테이블 속성 중 일부를 복제한 구조이다.

    • An auxiliary data structure that enables more efficient traverse and search than sequential scans순차 탐색보다 훨씬 효율적인 탐색과 검색을 가능하게 해주는 보조 자료구조이다.

• A motivating example:

  • SELECT * FROM Instructor WHERE name = ‘Katz’

    • DBMS literally have to look at every single row of the Instructor table to see if the name matches ‘Katz’
      DBMS는 'Katz'와 이름이 일치하는지 확인하기 위해 Instructor 테이블의 모든 행을 직접 확인해야 한다.

    • The purpose of having an index is to speed up search queries by cutting down the number of records/rows in a table that need to be examined
      인덱스의 목적은 검색 시, 확인해야 할 레코드 수를 줄여서 쿼리 속도를 높이는 것이다.

Example

• Index in action 인덱스 없이 수행되는 예제 쿼리

  • SELECT ICUSTAY_ID, DRUG, DOSE_VAL_RX, DOSE_UNIT_RX, ROUTE
    FROM PRESCRIPTIONS P
    WHERE P.DRUG LIKE 'amoxicillin%’ OR P.DRUG LIKE 'cefazolin’;

  • 걸린 시간 : 3s 935ms (execution :3s 841ms, fetching : 94ms)

• Index in action

  • CREATE INDEX PRESCRIPTIONS_idx04 ON PRESCRIPTIONS (DRUG);
    DRUG 컬럼에 인덱스를 생성하는 쿼리

  • SELECT ICUSTAY_ID, DRUG, DOSE_VAL_RX, DOSE_UNIT_RX, ROUTE
    FROM PRESCRIPTIONS P
    WHERE P.DRUG LIKE 'amoxicillin%’ OR P.DRUG LIKE 'cefazolin’;
    인덱스를 적용하면 해당 쿼리의 실행 속도가 개선된다.

  • 걸린 시간 : 410ms (execution : 371ms, fetching : 39ms)

Table Indexes

• Access types supported efficiently효율적으로 지원되는 접근 방식들

  • Records with a specified value in the attribute특정 속성과 일치하는 레코드 조회

  • Records with an attribute value falling in a specified range of values속성 값이 특정 범위에 속하는 레코드 조회

• Evaluation metrics

  • Access time 접근 시간

  • Insertion time 삽입 시간

  • Deletion time 삭제 시간

  • Space overhead 공간 오버헤드

• Basic concepts

  • Search-key: An attribute or set of attributes to look up records in a file검색키 : 파일에서 레코드를 조회하기 위한 속성 또는 속성들의 집합

    • Here ”key” differs from that used in primary key, candidate key, superkey, …여기서 말하는 '키'는 기본 키, 후보 키, 슈퍼 키와는 다른 개념이다.

    • Rather close to the “key” in the hash tables해시 테이블에서의 키 개념과 더 유사하다.

  • An index file consists of records (index entries) that form:
    인덱스 파일은 다음과 같은 형태의 레코드들로 구성된다.| search-key | pointer |

    • Index files are typically much smaller than the original table인데긋 파일은 읿란적으로 원래 테이블보다 훨씬 작다.

• Two basic kinds of indexes:

  • Ordered indexes: search-keys are stored in sorted order정렬 인덱스 : 검색키들이 정렬된 순서로 저장된다.

  • Hash indexes: search-keys are distributed uniformly across “buckets” using a hash function(s)해시 인덱스 : 해시 함수를 사용해 검색 키들을 균등하게 버킷에 분산시킨다.

• A table may have multiple indexes하나의 테이블은 여러 개의 인덱스를 가질 수 있다.

  • When the user execute queries, the DBMS figures out the best index(es) for each query사용자가 쿼리를 실행하면, DBMS는 가장 적합한 인덱스를 자동으로 선택한다.

  • Trade-off: performance (query optimization) vs. the number of indexes to create per database트레이드 오프 : 성능(쿼리 최적화)과 인덱스 수 (관리 복잡도) 사이의 트레이드오프가 존재한다.

    • Search overhead vs. Storage & maintenance overhead검색 성능 향상과 저장공간/유지 관리 비용 사이의 절충

• The DBMS ensures that the contents of the table and the index are logically in syncDBMS는 테이블과 인덱스의 데이터가 논리적으로 동기화되도록 유지한다.

  • When an attribute changes, the change is also applied to the index속성 값이 바뀌면, 해당 변경 사항은 인덱스에도 반영된다.

  • DBMSs are responsible for maintaining indexes and keep them synchronized with the underlying table인덱스를 관리하고, 테이블과 동기화하는 책임은 DBMS에 있다.

Agenda

• Database indexes 데이터베이스 인덱스

• Ordered indexes 정렬된 인덱스

  • Indexed-sequential files 순차 인덱스 파일

  • B+tree index files B+트리 인덱스 파일

    • B+tree nodes B+트리 노드

    • Queries on B+trees B+트리를 활용한 쿼리 처리

    • B+tree operations B+트리 연산

• Hash indexes (will not cover) 해시 인덱스 (본 자료에서는 다루지 않음)

• Inverted index 역방향 인덱스

Ordered Indexes

• Two types:

  • Indexed-Sequential Files순차 인덱스 파일

  • B+tree index filesB+트리 인덱스 파일

Indexed-Sequential Files

• In an ordered index, index entries are stored sorted on the search- key values정렬 인덱스에서 인덱스 항목들이 검색키 값 기준으로 정렬되어 저장된다.

• Few vocabs 몇 가지 용어 정리

  • Dense index: Index record appears for every search-key value in the file조밀 인덱스 : 파일 내의 모든 검색키 값마다 인덱스 레코드가 존재한다.

  • Sparse index: Contains index records for only some search-key values희소 인덱스 : 일부 검색키 값에 대해서만 인덱스 레코드를 가진다.

  • Clustering index: the index whose search-key specifies the sequential order of the file클러스터링 인덱스 : 검색키가 파일의 순서를 정의하는 인덱스

    • = Primary index 기본 인덱스

    • Usually (but not always) the primary key 보통은 기본 키가 클러스터링 인덱스가 되지만, 항상 그런 것은 아니다.

  • Non-clustering index: an index whose search-key specifies an order different from the sequential order of the file논클러스터링 인덱스 : 검색키가 파일의 순서와 다르게 정렬되는 인덱스

    • = Secondary index 보조 인덱스

• Example: dense index on the ID attribute of the instructor relation
  예시 : instructor 테이블의 ID 속성에 대한 조밀 인덱스

  • 왼쪽에 있는 것이 search-key이고, 인덱스 키는 포인터를 갖는다.

• Example: dense index on the dept_name attribute of the instructor relation (sorted on dept_name)
  예시 : instructor 테이블의 dept_name 속성에 대해 dept_name 기준으로 정렬된 조밀 인덱스

• Example: index on the ID attribute of the instructor relation
  예시 : instructor 테이블의 ID 속성에 대한 인덱스
  

  • Sparse index: applicable when records are sequentially ordered on search-key
    희소 인덱스는 레코드들이 검색키 기준으로 순서대로 정렬되어 있을 때 적합하다.
    

    • To locate a record with search-key value K:
      검색키 값 K를 가진 레코드를 찾기 위해
      

      • Find index record with largest search-key value < K
        K보다 작은 값 중 가장 큰 검색키 값을 가진 인덱스를 찾는다.

      • Search file sequentially starting at the record to which the index record points
        인덱스 레코드가 가리키는 위치부터 순차적으로 탐색을 시작한다.

• Example: Secondary index on the salary attribute of instructor
  예시 : instructor 테이블의 salary 속성에 대한 보조 인덱스
  

  • Secondary indices must be dense
    보조 인덱스는 반드시 조밀해야 한다.

  • Index record points to a bucket that contains pointers to all the actual records with that particular search-key value
    인덱스 레코드는 해당 검색키값을 가진 실제 레코드들의 포인터를 담은 버킷을 가리킨다.

Dense vs. Sparse Index

• Sparse index over dense index희소 인덱스가 조밀 인덱스보다 나은 점

  • Less space overhead공간 오버헤드가 적음

  • Less maintenance overhead for insertions and deletions삽입/삭제 시 유지보수 비용이 적음

  • Generally, slower than dense index for locating records다만, 레코드를 찾는 속도는 조밀 인덱스보다 느릴 수 있음.

Clustering vs. Non-Clustering Index

• Common rule of thumb: Indexes impose overhead on database modification일반적으로, 인덱스는 데이터베이스 수정 시 오버헤드를 유발한다.

  • When a record is inserted or deleted, every index on the relation must be updated레코드가 삽입되거나 삭제되면, 해당 릴레이션의 모든 인덱스를 업데이트해야 한다.

  • When a record is updated, any index on an updated attribute must be updated레코드가 업데이트 되면, 해당 속성의 인덱스도 함께 업데이트되어야 한다.

• Sequential scan using clustering index is efficient, but a sequential scan using a secondary (non-clustering) index is expensive on magnetic disk클러스터링 인덱스를 사용하는 순차 스캔은 효율적이다. 하지만, 보조 인덱스를 이용한 순차 스캔은 자기 디스크 상에서 비용이 많이 든다.

  • Each record access may fetch a new block from disk각 레코드 접근 시마다 새로운 디스크 블록을 불러와야 할 수 있다.

  • Each block fetch on magnetic disk requires about 5 to 10 milliseconds자기 디스크에서 블록을 가져오는 데에는 약 5~10 밀리초가 걸린다.

Indexes on Multiple Keys.

• Composite search-key복합 검색 키

  • E.g., index on the instructor relation on attributes (name, ID)예시 : instructor 테이블에서 (name, ID) 속성을 기반으로 한 인덱스

    • Values are sorted lexicographically값들은 사전식(사전순)으로 정렬된다.

      • E.g., (John, 12121) < (John, 13514) and (John, 13514) < (Peter, 11223)

    • One can query on just name, or on (name, ID)name 하나로도 쿼리가 가능하고, (name, ID) 복합 키로도 쿼리가 가능하다.

Agenda

• Database indexes 데이터베이스 인덱스

• Ordered indexes 정렬된 인덱스

  • Indexed-sequential files 순차 인덱스 파일

  • B+tree index files B+트리 인덱스 파일

    • B+tree nodes B+트리 노드

    • Queries on B+trees B+트리를 활용한 쿼리 처리

    • B+tree operations B+트리 연산

• Hash indexes (will not cover) 해시 인덱스 (본 자료에서는 다루지 않음)

• Inverted index 역방향 인덱스

B+Tree Index

• Motivation: Disadvantage of indexed-sequential files동기 : 순차 인덱스 파일의 단점 보완

  • Performance degrades as file grows, since many overflow blocks get created파일이 커질수록, 오버플로 블록이 많이 생겨 성능이 저하된다.

  • Periodic reorganization of entire file is required정기적으로 전체 파일을 재정렬해야 한다.

• Remedy: B+tree index files해결책 : B+트리 인덱스 파일

  • Automatically reorganizes itself with small, local changes, in the face of insertions and deletions삽입과 삭제가 있어도, 국소적인 구조 변경만으로 자동으로 균형을 맞춘다.

  • Reorganization of entire file is not required to maintain performance성능 유지를 위해 전체 파일을 재정렬할 필요가 없다.

  • (Minor) disadvantage of B+trees:B+트리의 (작은) 단점

    • Extra insertion and deletion overhead, space overhead삽입/삭제 시 추가적인 연산과 공간 오버헤드가 발생한다.

Trees

• Tree: A data structure representing hierarchical nature of a structure in a graphical form
  트리 : 구조의 계층적 특성을 시각적으로 표현하는 자료 구조이다.

• Tree: a set of linked nodes that does not have a cycle

  • Each nodes has zero or more child nodes각 노드는 0개 이상의 자식 노드를 가진다.

  • A child has at most one parent자식 노드는 최대 하나의 부모만 가질 수 있다.

  • A node without a parent is called root부모가 없는 노드는 루트라고 부른다.

  • A node with no children is called leaf자식이 없는 노드는 리프 노드라고 한다.

Terminologies

• Degree of a node: number of subtrees of a node노드의 차수 : 해당 노드가 가진 자식 수

  • E.g., degree of A = 3, C = 1, F = 0

• Degree of a tree: maximum degree of the node in a tree트리의 차수 : 트리 내 최대 차수를 가진 노드의 차수

  • E.g., degree of the tree =3 (A and D)

• Leaf (of terminal node): node with 0 degree리프 : 자식이 없는 노드

  • E.g., K, L, F, G, M, I, J

• Sibling: children of the same parent형제 노드 : 같은 부모를 가진 노드들

  • E.g., H, I, J are siblings

• Path: A sequence of nodes in which each node is adjacent to th next node경로 : 연결된 노드들의 순서

• Ancestors: All nodes along the path from root to the node조상 : 루트에서 현재 노드까지의 모든 노드

  • E.g., ancestors of M are A, D, and H

• Descendants: All nodes in subtrees자손 : 해당 노드의 서브트리에 포함된 모든 노드

  • E.g., descendants of B are E, F, K, and L

• Level of node: Let the root node be at level one; if a node is at level l, then its children are at level l+1노드의 레벨 : 루트는 1레벨, 자식은 그보다 1 높은 레벨

  • E.g., level of M = 4

• Height / depth of a tree: maximal level of any node in a tree트리의 높이/깊이 : 가장 깊은 노드의 레벨

Binary Search Trees

• Motivation: oftentimes we would like to search an arbitrary element efficiently동기 : 우리는 종종 임의의 요소를 효율적으로 검색하고 싶어 한다.

• Binary Search Trees: a tree which may be empty, or satisfy the following conditions이진탐색트리 : 비어 있을 수도 있고, 다음 조건을 만족하는 트리이다.

  • Every element has a unique key (value)모든 요소는 고유한 키(값)을 갖는다.

  • Keys in left subtree must be smaller than that of root왼쪽 서브트리의 키는 루트보다 작아야 한다.

  • Keys in right subtree must be larger than that of root오른쪽 서브트리의 키는 루트보다 커야 야한다.

  • Left and right subtrees are also binary search tree
    왼쪽과 오른쪽 서브트리 또한 이진 탐색 트리여야 한다.

• Binary Search Trees may not be a complete tree이진 탐색 트리는 반드시 완전 트리일 필요는 없다.

Binary Search Trees Issues이진탐색 트리의 문제점들

• Height of a binary search tree with n nodes노드가 n개인 이진 탐색 트리의 높이

  • Worst case (sorted order): n최악의 경우 (정렬된 입력) : n

  • Average case (random): O(log2n)평균적인 경우 (무작위 입력) : O(log2n)

Remedy: Balanced Trees해결책 : 균형잡힌 트리

• Self-balancing trees could alleviate the issue; e.g.,자기 균형 트리는 이 문제를 완화할 수 있다.

  • AVL tree

  • Red-black tree

  • B+tree

B+Tree

• B-Tree familyB-Tree 계열

  • B-Tree generally refers to a class of balanced tree data structures (B-tree and its variants)B-Tree는 일반적으로 균형 잡힌 트리 자료구조(B-Tree 및 그 변형들)의 한 종류를 의미한다.

  • Properties특징

    • Storage-friendly: B-trees work well on any layer of the storage hierarchy저장소 친화적 : B-Tree는 저장 계층의 어떤 단계에서도 잘 작동한다.

      • Work well on both disks and main memory디스크와 메인 메모리 모두에서 잘 작동한다.

    • Good performance on random and sequential accesses무작위 및 순차 접근에서 좋은 성능을 보인다.

      • Seeks/cache misses once for each node각 노드마다 한 번의 탐색/캐시 미스가 발생한다.

    • Universal applicability범용적인 적용 가능성

  • When people are mentioning B-Tree as a data structure, most likely they are referring to B+Tree사람들이 자료구조로서 B-Tree를 언급할 때, 대부분은 B+Tree를 의미한다.

    • B-Tree (1971)

    • B+Tree (1973)

    • B*Tree (1977?)

    • Blink-Tree (1981)

• B+Tree: a self-balancing tree that keeps data sorted and allows searches
  B+Tree : 데이터를 정렬된 상태로 유지하고, 검색을 가능하게 하는 자기 균형 트리이다.
  

  • B stands for "balanced”B는 'Balanced'의 약자이다.

  • It is a generalization of a binary search tree, in that a node can have more than two children이는 이진 탐색 트리의 일반화이며, 하나의 노드가 두 개 이상의 자식을 가질 있다.

  • Optimized for systems that read and write large blocks of data대량의 데이터를 읽고 쓰는 시스템에 최적화되어 있다.

  • Sequential access, insertions, and deletions are done in O(log n)순차 접근, 삽입, 삭제는 O(log n) 시간에 수행된다.

    • For a tree with n nodes, the distance between the root and any leaf node is always log nn개의 노드를 가진 트리에서 루트와 리프 노드 간의 거리는 항상 log n이다.

• B+tree is an M-way search tree with the following properties:
  B+Tree는 다음과 같은 특성을 가진 M-방향 탐색 트리이다.

  • M-way search tree:M-방향 탐색 트리

    • Multi-way tree (a generalized version of binary search trees)다방향 트리(이진 탐색 트리의 일반화된 버전)

    • Each node contains a maximum of M-1 elements and M children각 노드는 최대 M-1개의 요소와 M개의 자식 노드를 가진다.

  • Perfectly balanced; i.e., every leaf node is at the same depth
    완벽하게 균형 잡혀 있음; 즉, 모든 리프 노드가 동일한 깊이에 있다.

    • Distance to any leaf node is always log n모든 리프 노드까지의 거리는 항상 log n이다.

  • Every inner node (other than the root) is at least half-full루트를 제외한 모든 내부 노드는 최소 절반 이상 채워져 잇다.

    • M/2 - 1 ≤ #keys ≤ M-1

    • Every node has at least M/2 - 1 children모든 노드는 최소 M/2-1개의 자식을 가진다.

  • Special cases:특수한 경우

    • If the root is not a leaf, it has at least 2 children루트가 리프가 아니라면, 최소 2개의 자식이 있어야 한다.

    • If the root is a leaf (i.e., there are no other nodes in the tree), it can have between 0 and (M-1) values루트가 리프라면(즉, 트리에 다른 노드가 없다면), 0개에서 M-1개의 값을 가질 수 있다.

• An example B+tree (a 4-way B+tree)

Agenda

• Database indexes 데이터베이스 인덱스

• Ordered indexes 정렬된 인덱스

  • Indexed-sequential files 순차 인덱스 파일

  • B+tree index files B+트리 인덱스 파일

    • B+tree nodes B+트리 노드

    • Queries on B+trees B+트리를 활용한 쿼리 처리

    • B+tree operations B+트리 연산

• Hash indexes (will not cover) 해시 인덱스 (본 자료에서는 다루지 않음)

• Inverted index 역방향 인덱스

B+Tree

• An example B+tree (a 4-way B+tree)

B+Tree Nodes

• Typical B+tree nodes일반적인 B+트리 노드

  • | P1 | K1 | P2 | … | PM-1 | KM-1 | PM |

  • Ki are the search-key values (what are indexed)Ki는 검색 키 값이다. (인덱싱되는 대상)

  • Pi are pointers to children (for non-leaf nodes) or pointers to records or buckets of records (for leaf nodes)Pi는 (내부 노드의 경우) 자식 노드 포인터, 또는 (리프 노드의 경우) 레코드나 레코드 버킷을 가리키는 포인터이다.

  • The arrays are kept in sorted key order배열은 정렬된 키 순서를 유지한다.K1 < K2 < K3 < … < KM-1

• Non-leaf nodes
  내부 노드
  

  • All the search-keys in the subtree to which P1 points are less than K1
    P1이 가리키는 서브트리의 모든 키는 K1보다 작다.

  • For 2 £ i £ M – 1, all the search-keys in the subtree to which Pi points have values greater than or equal to Ki–1 and less than Ki
    2 <i < M - 1일 때, Pi가 가리키는 서브트리의 모든 키는 Ki-1 이상 Ki 미만이다.

  • All the search-keys in the subtree to which PM points have values greater than or equal to KM–1
    PM이 가리키는 서브트리의 모든 키는 KM-1이상이다.

  • | P1 | K1 | P2 | … | PM-1 | KM-1 | PM |

• Leaf nodes리프 노드

  • For i = 1, 2, ..., M-1, pointer Pi points to a file record with search-key value Ki.i = 1, 2, ..., M-1에 대해, 포인터 Pi는 검색 키 Ki를 갖는 파일 레코드를 가진다.

  • Search-keys are sorted : If Li, Lj are leaf nodes and i < j, Li's search-key values are less than or equal to Lj's search-key values검색 키는 정렬되어 있음 : Li, Lj가 리프 노드이고, i < j라면, Li의 키 값을 Lj보다 작거나 같다.

  • PM points to next leaf node in search-key orderPM은 검색 키 순서상 다음 리프 노드를 가리킨다.

• In commercial products, leaf node values may vary
  상용 제품에서는 리프 노드의 값 형태가 다를 수 있다.
  

  • For i = 1, 2, . . ., M–1, pointer Pi points to:

    • Use-case #1 (as discussed in the previous slide): Record IDs – a pointer to the location of the tuple that the index entry corresponds to
      사용 사례 #1 : 레코드 ID - 인덱스 항목이 가리키는 튜플의 위치 포인터
      

      • PostgreSQL, DB2, SQL Server, Oracle

    • Use-case #2: Tuple data – The actual contents of the tuple is stored in the leaf node
      사용 사례 #2 : 튜플 데이터 - 튜플의 실제 내용이 리프 노드에 저장된다.
      

      • Secondary indexes have to store the record ID as their values
        보조 인덱스는 레코드 ID를 값으로 저장해야 한다.

      • More complicated
        구조조 더 복잡하다.

      • MySQL, SQLite, SQL Server, Oracle

Another Example B+Tree또 다른 B+Tree 예시

• B+tree for instructor (degree=6 or 6-way B+tree)강사용 B+트리 (차수 = 6, 6방향 B+Tree)

  • Leaf nodes must have between 3 and 5 values
    리프 노드는 3개에서 5개의 값을 가져야 한다.
    

    • ∵ é(M–1)/2ù and M–1, with M = 6

  • Non-leaf nodes other than root must have between 3 and 6 children
    루트를 제외한 내부 노드는 3개에서 6개의 자식을 가져야 한다.
    

    • ∵ é(M/2ù and M with M = 6

  • Root must have at least 2 children
    루트는 최소 2개의 자식을 가져야 한다.

Observations관찰 사항

• Since the inter-node connections are done by pointers, “logically” close blocks need not be “physically” close노드 간 연결은 포인터로 되어 있으므로, "논리적으로" 가까운 블록이 "물리적으로" 가까울 필요는 없다.

  • The non-leaf levels of the B+tree form a hierarchy of sparse indexesB+트리의 비리프 레벨은 희소 인덱스의 계층을 형성한다.

• The B+tree contains a relatively small number of levelsB+Tree는 상대적으로 적은 수의 레벨을 가진다.

  • If there are K search-key values in the file, the tree height is no more than élogén/2ù(K)ù ⇒ searches can be done efficiently파일에 K개의 검색 키가 있을 경우, 트리 높이는 [log[n/2](K)] 이하이다. -> 탐색이 효율적이다.

    • Level below root has at least 2* én/2ù values루트 바로 아래 레벨은 최소 2 * [n/2] 개의 값을 가진다.

    • Next level has at least 2* én/2ù * én/2ù values그 다음 레벨은 최소 2 * [n/2] * n[/2] 개의 값을 가진다.

    • … and so forth

• Insertions and deletions to the main file can be handled efficiently, as the index can be restructured in logarithmic time (we’ll see)멩니 파일에 대한 삽입과 삭제는 로그 시간 내에 인덱스를 재구성함으로써, 효율적으로 처리될 수 있다.

Agenda

• Database indexes 데이터베이스 인덱스

• Ordered indexes 정렬된 인덱스

  • Indexed-sequential files 순차 인덱스 파일

  • B+tree index files B+트리 인덱스 파일

    • B+tree nodes B+트리 노드

    • Queries on B+trees B+트리를 활용한 쿼리 처리

    • B+tree operations B+트리 연산

• Hash indexes (will not cover) 해시 인덱스 (본 자료에서는 다루지 않음)

• Inverted index 역방향 인덱스

Queries on B+Trees

function find(v)
    1. C=root
    2. while (C is not a leaf node)
        1. Let i be least number s.t. V £ Ki
        2. if there is no such number i then
        3. Set C = last non-null pointer in C
        4. else if (v = C.Ki ) Set C = Pi +1
        5. else set C = C.Pi
    3. if for some i, Ki = V then return C.Pi
    4. else return null /* no record with search-key value v exists. */

• Range queries find all records with search-key values in a given range범위 쿼리는 주어진 범위의 검색 키 값을 가진 모든 레코드를 찾는다

  • function findRange(lb, ub) which returns set of all such records is available in the textbook
    그러한 모든 레코드의 집합을 반환하는 함수 findRange(lb, ub)는 교과서에서 제공된다.

  • Real implementations usually provide an iterator interface to fetch matching records one at a time, using a next() function
    실제 구현에서는 일반적으로 next() 함수를 사용하는 반복자 인터페이스를 제공하여, 일치하는 레코드를 하나씩 가져온다.

• Time complexity: If there are K search-key values in the file, the height of the tree is no more than élogén/2ù(K)ù
  시간 복잡도 : 파일에 K개의 검색 키가 있다면, 트리의 높이는 [log [n/2] (k)]를 넘지 않는다.

• A node is generally the same size as a disk block, typically 4 KB노드는 일반적으로 디스크 블록과 같은 크기이며, 보통 4KB이다.

  • and M is typically around 100 (40 bytes per index entry)그리고 M은 보통 100 정도이다. (인덱스 항목당 400바이트 기준)

• With 1 million search-key values and M = 100100만 개의 키 값과 M=100일 때,

  • At most log50(1,000,000) = 4 nodes are accessed in a lookup traversal from root to leaf루트에서 리프까지의 탐색에서 최대 log50(1,000,000) = 4개의 노드가 접근된다.

  • C.f., a balanced binary tree with 1 million search-key values — around 20 nodes are accessed in a lookup참고로, 100만 개의 검색 키 값을 가진 균형 잡힌 이진 트리에서는 검색 시 20 개의 노드가 접근된다.

Agenda

• Database indexes 데이터베이스 인덱스

• Ordered indexes 정렬된 인덱스

  • Indexed-sequential files 순차 인덱스 파일

  • B+tree index files B+트리 인덱스 파일

    • B+tree nodes B+트리 노드

    • Queries on B+trees B+트리를 활용한 쿼리 처리

    • B+tree operations B+트리 연산

• Hash indexes (will not cover) 해시 인덱스 (본 자료에서는 다루지 않음)

• Inverted index 역방향 인덱스

B+Tree OperationsB+Tree의 연산

• Insertion

  • 1. Find the proper leaf node L for the newly inserted key새로 삽입할 키에 대해 적절한 리프 노드 L을 찾는다.

  • 2. Put data entry into L in sorted order데이터를 정렬된 순서로 L에 삽입한다.

  • 3. If L has enough space, doneP에 공간이 충분하다면 완료한다.Otherwise, split L: . . . . a half of the keys stay in L그렇지 않으면, L을 분할한다.another half goes to a new node L2나머지 절반은 새 노드 L2로 이동한다.

    • Redistribute entries evenly엔트리들을 균등하게 재배치해야 한다.

    • Insert index entry pointing to L2 into the parent of LL2를 가리키는 인덱스 항목을 L의 부모에 삽입한다.

• Demo: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html(Algorithm Visualizations, David Galles)

Insertion (cont’d)

• Splitting a leaf node:리프 노드를 분할하기

  • Take the M (search-key, pointer) pairs, including the one being inserted, in sorted order삽입할 키를 포함하여, M개의 (검색 키, 포인터) 쌍을 정렬된 순서로 가져온다.

  • Place the first éM/2ù in the original node, and the rest in a new node처음 [M/2] 개는 원래 노드에, 나머지는 새 노드에 넣는다.

  • Let the new node be p, and let k be the least key value in p. Insert (k,p) in the parent of the node being split새 노드를 p라고 하고, p에서 가장 작은 키 값을 k라고 하자. (k, p)를 분할된 노드의 부모에 삽입한다.

  • If the parent is full, split it and propagate the split further up (splitting of nodes proceeds upwards till a node that is not full is found)부모가 가득 찼다면, 부모도 분할하고 그 분할을 위로 전파한다. (가득 차지 않은 노드를 찾을 때까지 분할이 위로 진행된다.)

    • In the worst case the root node may be split increasing the height of the tree by 1최악의 경우, 루트 노드도 분할되며, 트리의 높이는 1만큼 증가할 수 있다.

• Splitting a non-leaf node: when inserting (k,p) into an already full internal node N(k, p)를 이미 가득 찬 내부 노드 N에 삽입될 때

  • Copy N to an in-memory area S with space for M+1 pointers and M keysN을 메모리 공간 S에 복사하며, S에는 M+1개의 포인터와 키 공간이 있따.

  • Insert (k,p) into S(k, p)를 S에 삽입한다.

  • Copy P1,K1, …, K éM/2ù-1,P éM/2ù from S back into node NS에서 P1, K1, ..., K[M/2]-1, P[M/2]를 노드 N으로 다시 복사한다.

  • Copy PéM/2ù+1,K éM/2ù+1,…,KM,PM+1 from S into newly allocated node N’S에서 P[M/2] + 1, K[M/2] + 1, ..., KM, PM+1을 새로 생성된 노드 N`으로 복사한다.

  • Insert (K éM/2ù,N') into parent N(K[M/2], N`)을 부모 노드 N에 삽입한다.

B+Tree Insertion

B+Tree Operations

• Deletion

  • 1. Start at root, find leaf L where entry belongs루트에서 시작하여여 항목이 있는 리프 노드 L을 찾는다.

  • 2. Remove the entry해당 항목을 제거한다.

  • 3. If L is at least half-full, doneL이 최소 절반 이상 차 있다면, 완료한다.If L has only M/2-1 entriesL에서 M/2-1 개의 항목만 있다면,

    • Try to rebalance, by borrowing a key from a sibling형제 노드로부터 키를 빌려, 균형을 맞추려고 시도한다.

  • 4. If a merge occurred, one must delete its entry from the parent of L병합이 발생했다면, L의 부모로부터 해당 항목을 삭제해야 한다.

    • If redistribution fails, merge L and one of its sibling재분배가 실패하면, L과 형제 노드 중 하나를 병합한다.

• Demo: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html(Algorithm Visualizations, David Galles)

B+Tree Deletion

Remarks on B+Tree Deletion

• The node deletions may cascade upwards till a node which has éM/2ù or more pointers is found노드 삭제는 [M/2] 개 이상의 포인터를 가진 노드를 찾을 때까지 위로 연쇚거으로 진행될 수 있다.

• If the root node has only one pointer after deletion, it is deleted and the sole child becomes the root삭제 후 루트 노드에 포인터가 하나만 남는다면, 루트는 삭제되고 해당 자식 노드가 새로운 루트가 된다.

Indexes with B+Trees

• Key take-homes

  • No need to search whole table (time efficient)전체 테이블을 검색할 필요 없다. (시간 효율적)

  • No need to explicitly sort data데이터를 명시적으로 정렬할 필요 없다.

  • Insertions and deletions can be done in logarithmic time삽입과 삭제는 로그 시간에 수행될 수 있다.

  • Use extra space (replica of a subset of data)추가 공간을 사용한다. (데이터 일부를 복제한다)

Agenda

• Database indexes

• Ordered indexes

  • Indexed-sequential files

  • B+tree index files

    • B+tree nodes

    • Queries on B+trees

    • B+tree operations

• Hash indexes (will not cover)

• Inverted index

Inverted Index

• Observation관찰 사항

  • The tree indexes that we have discussed so far:지금까지 우리가 논의한 트리 인덱스는

    • Useful for "point" and "range" queries"지점" 및 "범위" 쿼리에 유용하다.

      • Find all customers in zip code = 15213우편 번호 15213에 있는 모든 고객 찾기

      • Find all orders between June 2018 and September 20182018년 6월과 9월 사이의 모든 주문 찾기

  • They are NOT good at keyword searches:그러나 키워드 검색에는 적합하지 않다.

  • Find all Wikipedia articles that contain the word "Soccer""Soccer"라는 단어를 포함한 모든 위키피디아 문서 찾기

• Inverted Index
  역색인

  • An inverted index stores a mapping of words to records that contain those words in the target attribute역방항 인덱스는 대상 속성에 있는 단어들을 해당 단어를 포함하는 레코드와 매핑하여 저장한다.

    • Sometimes called a full-text search index때로는 전체 텍스트 검색 인덱스라라 부른다.

    • Also called a concordance in old contexts과거 문맥에서는 콘코던스라고 불린다.

  • The major DBMSs support these natively주요 DBMS는 이를 기본적으로 지원한다.

    • MySQL: https://dev.mysql.com/doc/refman/8.0/en/innodb-fulltext-index.html

      • One has to use InnoDB as one’s DB engine, and special queries to look upInnoDB를 DB엔진을 사용하고 특수 쿼리를 사용해야 한다.

  • There are also specialized DBMSs또한 전문화된 DBMS들도 있다.

    • Lucene, Solr, Elasticsearch, Sphinx, Xapian

KUBiC: Korea Unification Bigdata Center

• A government-funded project on a data-center development focusing on the Korean unification한국 통일을 중심으로한 데이터 센터 개발을 위한 정부 지원 프로젝트

• URL: https://kubic.handong.edu/

• Data archive + search engine + web-based analysis tools, specialized on the Korean unification and North Korea research한국 통일 및 북한 연구에 특화된 데이터 아카이브 + 검색엔진 + 웹 기반 분석 도구

• Contains 20,000+ academic papers and government reports on the relevant topics관련 주제에 대한 2만 편 이상의 학술 논문 및 정부 보고서를 포함한다.

Inverted Index

Indexer steps: Token sequence

• Sequence of (Modified token, Document ID) pairs(수정된 토큰, 문서 ID) 쌍의 시퀀스

• Doc1 : I did enact Julius Caesar I was killed i’ the Capitol; Brutus killed me.

• Doc2 : So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious

Indexer steps: Sort

• Sort by terms용어 별로 정렬

  • And then docID
    그리고 문서 ID로 정렬

  • This is the core indexing step
    이것이 인덱싱의 핵심 단계이다.

Indexer steps: Dictionary & Postings

• Multiple term entries in a single document are merged하나의 문서 내 여러 용어 항목이 병합된다.

• Split into Dictionary and Postings사전과 포스팅으로 분리된다.

• Doc. frequency information is added문서 빈도 정보가 추가된다.

Inverted Index

• For each term t, we must store a list of all documents that contain t각 용어 t에 대해 t를 포함하는 모든 문서의 목록을 저장해야 한다.

  • Identify each doc by a docID, a document serial number각 문서는 docID, 즉 문서 일렬번호로 식별된다.

  • Can we use fixed-size arrays for this?이를 위해 고정 크기 배열을 사용할 수 있을까?

    • In memory, can use linked lists or variable length arrays메모리에서 linked list 또는 가변 길이 배열을 사용할 수 있다.

Query Processing

• How do we process a query, using the index we just built?우리가 방금 구축한 인덱스를 사용하여 쿼리를 어떻게 처리해야 할까?

• Query processing: AND쿼쿼 처리 : AND 연산

  • E.g., Consider processing the query:예 : 다음 쿼리를 처리한다고 가정하자

    • Brutus AND Caesar

      • Locate Brutus in the Dictionary;사전에서 Brutus를 찾는다.

        • Retrieve its postings해당 포스팅을 가져온다.

      • Locate Caesar in the Dictionary;사전에서 Caesar를 찾는다.

        • Retrieve its postings해당 포스팅을 가져온다.

      • “Merge” the two postings (intersect the document sets):두 포스팅을 "병합"한다. (문서 집합을 교차시킴)

• E.g., (cont’d)

  • Walk through the two postings simultaneously, in time linear in the total number of postings entries
    전체 포스팅 항목 수에 대해 선형 시간으로 두 포스팅을 동시에 순환한다.

Inverted Index

Ranking Algorithms

• Inverted index simply offers the list of documents that contain the search-word역방향 인덱스는 검색어를 포함한 문서 목록만을 제공한다.

• Ranking/ordering of the search results lets the users access important documents earlier/easier검색 결과의 랭킹/정렬은 사용자가 더 중요한 문서에 더 빠르고 쉽게 접근할 수 있도록 해준다.