계산수론프로젝트최종보고서 (Subject: A Survey on Index Data Structures) 소속 : 전기 컴퓨터공학부학번 : 2007-30219 성명 : 김진일 1. 개요 (Introduction) (1) Index의정의컴퓨터공학에서 'index' 라는단어는여러가지중의적인의미로사용되는데그중대표적인의미들을꼽자면 1 배열의원소를나타내는정수, 2 데이터에대한접근 (lookup) 을빠르게하는자료구조, 3 검색엔진에서정보를빠르게추출하기위한과정등이있다. 이프로젝트에서는 index의의미를두번째의미로한정하여다양한 index 자료구조에대하여다량의데이터가주어진경우각각의 index가이데이터들을어떻게저장하고접근하며갱신해나가는지에대하여다루고자한다. [1, 2] (2) Index의평가기준 Index는다양한기준을통하여평가할수있는데대상이되는데이터의타입이고정된경우원하는데이터에접근하는시간 (lookup time), 새로운데이터가추가되거나기존데이터가삭제되는경우 index를갱신하는시간 (update time), index에데이터를무한히넣을때 index가어느정도까지좋은성능을보이는지 (scalability) 등을비교하여평가할수있다. 여기서는데이터타입별로 select, insert, delete 연산의수행시간을 asymtotic하게평가하여다양한 index들을비교하도록하겠다. 그리고필요한경우실제구현상에서나타날수있는문제점에대해서도함께설명하겠다. (3) Index의종류 Index는자료구조가저장되는위치에따라크게 in-memory index와 external index로구분할수있다. In-memory index는 index의모든정보가 word 단위 ( 혹은 byte 단위 ) 로접근가능한 memory에저장되는 index를의미하고 external index는 index의대부분의정보가 block 단위 ( 보통수천 byte에서수백만 byte) 로접근가능한 disk에저장되는 index를의미한다. 보통 memory의속도가 disk의속도에비해매우빠르므로 in-memory index는 index의연산시간 (CPU 연산의 time complexity) 를중심으로평가하는반면 external index 는 disk I/O 횟수를중심으로 index의성능을평가한다. 그러므로같은 idea에의해구성된 index라도구현되는위치에따라다른형태를띄게된다. 일반적으로 external index가더 general한가정에서동작하므로더복잡한형태를가진다. (4) 프로젝트의목적과범위이프로젝트에서는 index 자료구조에대한개요를전달하고자주사용하는 index에대하 - 1 -
여간단하게소개하는것이목적이다. 그러므로각각의 index에대하여자세하게설명하기보다는 index의기본아이디어와특징을간단하게소개하고상황에맞게 index를사용할수있도록 index의성능을정리하고자한다. Index를구성하는기본아이디어에있어서는 in-memory index와 external index에큰차이가없으므로여기서는 in-memory index를대상으로가장자주쓰이는수치데이터 (numeric data) 에대한 index를중심으로설명하고부가적으로문자열데이터 (string data), 다차원데이터 (multi-dimensional data) 에대한대표적인 index를소개하도록하겠다. (5) 보고서구성먼저 2장에서는배경지식으로 time complexity 분석기법중한가지인 amortized analysis에대하여설명한다. 그리고 3장에서수치데이터에대한다양한 index들을간략하게소개하고 4장에서문자열데이터와다차원데이터에대한대표적인 index를소개한다. 5 장에서보고서내용을정리하면서결론을내린다. 그리고 6장은참고문헌의리스트이다. 2. 배경지식 (Amortized Analysis) 어떤알고리즘이내부에특정오퍼레이션을반복적으로수행하는경우해당알고리즘의최악의시간은각각의오퍼레이션이최악수행시간에오퍼레이션호출횟수를곱하면계산할수있다. 그런데때때로이와같은분석결과가정확한최악수행시간을계산하지못하고수행시간을과장하여예측하게되는측면이있는데이와같은경우시간복잡도를분석하는기법이 amortized analysis 기법이다. [1] 좀더구체적으로말하자면 amortized analysis는어떤 operation의 sequence를분석하기위한테크닉으로 operation의 sequence에대해 tight한 bound를계산하는방법이다. Amortized analysis는분석결과로최악의 operation sequence에대한 operation 1회의평균적인 cost를계산하게되는데이를 amortized cost라고한다. Amortized cost는평균값의일종이지만입력의분포와는무관하므로확률과무관한 최악 operation sequence에대한평균 operation cost' 임을유의하자. Amortized analysis의한예로 stack에일반적인 push, pop과한꺼번에 k개의원소를 pop할수있는 multi-pop 연산을정의한 multi-pop stack을생각해보자. Push와 pop은 시간에수행할수있는반면 multi-pop은 시간을필요로한다. 개의원소가 multi-pop stack에들어있는경우 이면 multi-pop은최대 시간을사용할수있다. 이때 번의 operation을수행하는경우최악의경우수행시간을 로분석할수있다. 그러나보다정확하게분석하면이경우최악의경우에도 시간에모든연산이수행될수있음을증명할수있으므로 [1] multi-pop 연산의 amortized cost는 이라고할수있다. 3. 수치데이터에대한 index 수치데이터에대한 index의수행시간은 index에저장된데이터의개수를 이라고할때 에대한함수로표현할수있다. - 2 -
(1) Array a) Naive array 수치데이터를저장할수있는가장간단한형태는데이터를 array에임의의순서로저장하는것이다. 이경우 select는 linear scan으로 시간, insert는끝에추가하여 시간, delete는삭제할원소를 linear scan으로찾은후 array 원소들을한칸씩이동하여 시간에동작할수있다. 이경우데이터가많은경우에는 select, delete 연산을수행할때마다긴시간이소요되므로사용하기적절하지않다. 그림 1. Naive array 예제 b) Sorted array 데이터가고정된경우 array를 sorted order로유지하는것만으로도상당한효과를얻을수있다. 일단데이터를 시간에걸쳐서한번 sorting하고나면 binary search를통하여 select를 시간에수행할수있다. 그러나 insert, delete는데이터 shift가필요하므로 시간을필요로하여데이터가자주 update되는경우비효율적이다. 그림 2. Sorted array 예제 c) Dynamic table 실제구현에서 array를사용하는경우 array의크기를할당할때미리결정해야하므로최종적으로들어가게되는원소의개수를모르는경우구현자가적절한크기를미리예상하여할당해야하는불편함이있다. 이경우구현자의예상보다현저히적은수의데이터가들어오는경우공간을비효율적으로사용하게되고예상보다많은수의데이터가들어오는경우프로그램이비정상적으로동작하게된다. 이경우사용할수있는기법중한가지가 dynamic table이다. [1] Dynamic table은처음에작은크기의 array를할당하여사용하다가 array가가득차게되면 2배의크기의 array를새로할당한다음원래 array에서새 array로데이터를복제하고원래 array의메모리를해제하는방법이다. Naive array에 dynamic table 기법을적용하면 insert를반복할때메모리확장이나타나는시점에일시적으로 시간을필요로하지만 insert sequence의평균을취하면 (amortized cost) 시간에수행할수있다. 그러므로 dynamic table은메모리를실제사용량의 2배이내로항상유지하면서 cost는 amortized하게그대로유지하는좋은기법이라고할수있다. Dynamic table은 C++ STL의 vector나 Java의 ArrayList class에구현되어있으므로쉽게사용할수있다. (2) List 데이터를저장하는또다른간단한기법으로 linked list가있다. Linked list는각각의원소를 node에저장하고 node들을포인터로서로연결하여저장하는기법이다. Array와달리실제데이터가들어올때마다메모리를할당하여확장할수있고가운데원소를추가하거나삭제하는데 시간이걸리므로유연한자료구조라고할수있다. 그러나데이터를 - 3 -
sorting하여도 linear scan을피할수없으므로 select에 시간, insert ( 맨마지막에추가 ) 시간, delete 시간으로느리다는단점을가진다. 그림 3. List 예제 (3) Search Tree Search tree는 sorting된 array가 시간에빠르게데이터에접근하는특성과 list가데이터의추가 / 삭제를빠르게수행할수있는장점을결합한자료구조이다. a) Binary Search Tree (BST) Binary search tree는 [ 그림 4] 와같은형태의자료구조로 tree 형태로구성되어각각의 node마다한원소를가지는데각각의 node의왼쪽 subtree에는 node가저장한값보다작은값들이저장되고오른쪽 subtree에는 node 값보다큰값들이저장되는자료구조이다. 그림 4. Binary Search Tree 예제. 오른쪽은 node 10 을삭제한후이다. 그림 5. Binary Search Tree 의최악의경우 BST에서 select와 insert는 root로부터 leaf에도달할때까지찾고자하는값과 node의값을비교하여작으면왼쪽 node, 크면오른쪽 node로진행하면쉽게수행할수있다. Delete는삭제되는 node를대신할 node를찾아대체하면된다. BST는 tree의높이가 이면 select, insert, delete를모두 시간에수행할수있으므로평균적으 - 4 -
로 수행시간을가지는자료구조이다. 그러나 [ 그림 5] 와같이최악의경우에는 BST가 linked list와같은모습으로퇴화하여모든연산이 시간이걸리게될수있다는문제점을가지고있다. b) Balanced Search Tree Balanced search tree는 BST가최악의경우 unbalanced 단점을보완한 search tree로 tree의높이를자동으로조정해주는특징이있다. Balanced search tree는 1962년 Adel'son과 Velskii, Landis가제안한 AVL tree가처음제안된이래 1970년 Hopcroft에의해제안된 2-3 tree, 1972년 Bayer와 McCreight에의해제안된 B-tree, 그리고역시 1972 년 Bayer에의해제안된 red-black tree, 그리고 1993년 Andersson에의해제안된 AA-tree로발전되어왔다. [2] 처음제안된 AVL tree는각각의 node가높이정보를가지고오퍼레이션중에높이를조절하여 root로부터 leaf까지가장 path와가장짧은 path의길이가 2 이하가되도록유지하는구조를가지고있었다. 그러나알고리즘이복잡하여구현이어렵고각각의 node가차지하는공간이큰문제점이있었다. 2-3 tree는각각의 node가최대 2개의원소를가지고 2개혹은 3개의자식을가지게하여 AVL tree보다간단한방법으로 tree의높이를모두같게유지하였다. 그런데 2-3 tree는알고리즘에서 root에서 leaf까지내려갔다가 leaf에서 root로역추적하면서 tree의형태를바로잡아야하는번거로움이있었다. 이를개선한 B-tree는 2-3 tree와유사하게각각의 node가지정된개수 (k개) 이하의자식을가지는 tree로 root에서 leaf로가면서 tree의형태를바로잡아역추적의번거로움을없애고각각의 node가가지는자식의최대개수를 4개이상의임의로짝수로설정할수있게하였다. 2-3 tree나 B-tree와같이자식을여러개가지는경우일부공간을낭비하게되는데이를개선하여 binary search tree 형태로개선한알고리즘이 red-black tree이다. Red-black tree는 root 에서 leaf로가는 path의길이가최대 2배이하로차이나게하는근사적인 balancing을하는알고리즘으로개념적으로직관적이고각각의 node당 1bit 추가메모리만사용하므로널리사용되고있다. AA tree는 red-black tree의단점을일부개선한 search tree이다. 현재까지 balanced search tree 중널리사용되는알고리즘은 B-tree와 red-black tree이므로이들에대하여간략하게소개하겠다. b-1) B-tree B-tree는 시간에 select, insert, delete를수행할수있는유연한 tree 구조로각각의 non-leaf node가 2개혹은 3개의자식을가지고모든 leaf node가같은높이를가진다는특징이있다. B-tree은 join과 split 연산 [ 그림 7, 8] 을이용하여높이를조절하는데높이가커질때에는항상 root node의 split에의해 tree가위로커지므로아래에서부터위로증가하는특징을가진다고할수있다. 그림 6. B-tree 의예제 - 5 -
그림 7. B-tree 의 join 예제. (insert 'I') 그림 8. B-tree 의 split 예제 (insert 'H') 그림 7은 B-tree의 join 예제를보여준다. I를추가하기에앞서 DEF node의 E를 CK node에 join하여 I를추가할수있는공간을만든다. 그리고생긴공간에 I를추가한다. 그림 8은 B-tree의 split 예제를보여주는데 H' 를추가하기전에 CEK node를분할하여높이를증가시키고 H를추가한다. Join과 split을최대 만큼반복되므로연산들의복잡도에는영향을주지않는다. b-2) Red-Black tree Red-black tree는각각의 node가 red 또는 black의 color를가지는 binary search tree로 root에서 leaf로가는가장짧은 path의길이와가장긴 path의길이가 2개이하차이나는특징을가지는 balanced search tree이다. [ 그림 9] Red-black tree는다음의 red-black property를가진다. 1 모든 node는 red 또는 black이다. 2 root는 black이다. 3 모든 leaf는 black이다. (leaf는모두 black인 nil node인데그림에서는표시하지않았다.) 4 어떤 node가 red이면자식은모두 black이다. (red는 parent-child로연속되지않음 ) 5 root에서 leaf로가는모든 path에는동일한개수의 black node가존재한다. 그림 9. Red-black tree 의예제 - 6 -
Red-black tree의높이는 rotation에의해조절하는데연산수행시 tree를따라가면서 red-black tree property를유지할수있도록 tree의형태를유지해나간다. ( 자세한사항은 [1] 참조 ) [ 그림 10] 은 'I' 를추가하는과정에서 rotation이나타나는예를보여준다. 그림 10. Red-black tree 의 rotation 예제 (insert 'I') (4) Hash Table Hash table은 table(array로생각 ) 에 key와 value를가지는데이터를저장하는자료구조로 hash function이라고불리는함수를이용하여 key를 array의 index로변환한다. Hash table 의크기가데이터의크기의상수배정도일때 hash function이데이터들을 hash table 상에고루나눠주면 hash table 상에서 select, insert, delete가 시간에수행할수있으므로 hash table은데이터의양이매우많은경우매우효율적인자료구조이다. 그러나최악의경우연산시간이 시간까지늘어날수있고 hash function 값이같은 key들을처리할 collision resolution 방법이필요하다는점에서신중하게사용하여야한다. 실제구현할때에는여러가지어려움이있을수있는데먼저좋은 hash function의계산이느릴수있고 hash function이고르면 table에대한접근의 locality가적으므로 cache의도움을받기어렵다. 그리고 hash table을조작하는방법이복잡해질수록 error가발생하기쉽고사용자가데이터의특성을고려하여 hash function, table size, collision resolution 방법등을모두결정하여야하므로사용하기가까다롭다는단점이있다. 그러므로 hash table은데이터의여러가지특징을고려하여신중하게사용하여야한다. - 7 -
(5) 성능요약 (summary) 그림 11. 수치데이터에대한 index 의성능요약 4. 기타데이터에대한 index (1) 문자열데이터에대한 index 문자열데이터 (string data) 에대한대표적인 index로 suffix tree를들수있다. Suffix tree 는어떤 string S에대하여 S의모든 suffix를 root에서 leaf로가는 path로가지는 tree로 pattern matching이나 LCA (Longest Common Ancestor) 와같은 string operation들을빠르게수행할수있도록해주는자료구조이다. [3] [ 그림 12] 는 S=BANANA$ 에대한 suffix tree의예를보여준다. S의모든 suffix가 tree의 root로부터의 path에포함되어있음을쉽게확인할수있다. 그림 12. S=BANANA$ 에대한 suffix tree Suffix tree 를만드는데걸리는시간은 인데 [3] S 의모든 suffix 의길이의합이 - 8 -
임을고려하면 suffix tree를효율적으로만들수있음을알수있다. 일단 suffix tree를만들고나면여러 string operation을빠르게수행할수있는데한예로 [ 그림 12] 의 S에서 pattern P=NAN을찾고싶다면 suffix tree에서단순히 NAN을따라가면된다. 도착한 leaf node가 S의 3번째글자 (position 2) 를가리키고있으므로 S의 3번째글자부터 NAN 이나타남을확인할수있다. 즉 S에서 pattern P를찾는데 시간이걸리므로매우효율적으로 pattern을찾을수있음을알수있다. (2) 다차원데이터에대한 index 다차원데이터에대한 index의한가지로 1984년 Antonin Guttman에의해제안된 R-tree 를들수있다. R-tree는 B-tree와같은방법으로 balance를유지하는다차원데이터에대한 balanced search tree이다. R-tree는다차원공간을계층적인 bounding rectangle들로쪼개어관리한다. 저장데이터들은모두 R-tree의 leaf node에저장되고 R-tree의 non-leaf node들은자식들이가지는데이터혹은 bounding rectangle들을모두포함하는 bounding rectangle을가진다. 그림 13. R-tree 의예 그림 14. [ 그림 13] 의 2 차원범위분포 [ 그림 13] 과 [ 그림 14] 는 2차원공간상에서 R-tree와 R-tree의점들이저장된공간을보여주는데예를들어 node R8 아래의데이터들은모두 R8의 bounding rectangle 내에포함된다. 그리고 node R3의 bounding rectangle은 node R8, R9, R10의 bounding - 9 -
rectangle을모두포함한다. Node R1의 bounding rectangle은 node R3, R4, R5의 bounding rectangle을포함하는더큰 rectangle이다. R-tree에서 insert와 delete는가까운원소들이최대한같은 leaf node에할당되도록진행되고 bounding box의크기를최소로유지할수있도록진행된다. Select는찾고자하는점을포함할수있는 bounding rectangle을가지는모든 node들을 traverse하면서찾게된다. 이때대부분의 node들은볼필요가없으므로 R-tree의연산은평균적으로 시간에수행된다. 5. 결론 이프로젝트에서는자주사용하는 index에대하여간략하게소개하고각각의 index가가지는성능을정리하였다. 살펴본결과수치데이터에대해서는데이터의크기가작은경우에는구현이단순한 array나 list를사용하는것이바람직하고데이터의개수가많아지면효율적인관리가필요하므로 binary search tree나 hash table을쓰는것이바람직해보인다. 특히데이터의 update가없는경우 array에 sorting만해놓아도좋은성능을낼수있었다. 그러므로실제사용하는 index를고를때에는수행시간뿐아니라구현의용이성, 사용메모리, 데이터의개수와분포, update 빈도등다양한측면을종합적으로고려하여야한다는결론을내릴수있다. 그리고문자열데이터나다차원데이터등다른형태의데이터에대해서는각각다른형태의최적화된 index가존재함을확인하여데이터에따라 index가다른모습이됨을볼수있었다. 6. 참고문헌 (References) [1] Introduction to Algorithms, (Second Edition) Thomas H. Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein, MIT Press, 2001. [2] Wikipedia, http://wikipedia.org [3] A space-economical suffix tree construction algorithm, Edward M. McCreight, Journal of ACM 23 (2): 262-272. [4] R trees: A dynamic index structure for spatial searching, Antonin Guttman, In proc. ACM SIGMOD International Conference on Management of Data, page 47-57, Boston, June 1984. - 10 -