전체 글291 [Indexing]B+ tree deletion 노드에서는 최소 만족해야하는 개수 기준이 있다. 이 기준을 deletion에도 기준을 유지시켜야 한다. 첫 번째 전략은 merge, 형제 노드와 merge하고 부모 노드를 업데이트한다. 두 번째 전략은 redistribute, 형제의 것을 빌려와 사용한다. n=4이고 leaf의 최소 키의 개수는 C((4-1)/2)= 2 이므로 삭제하게 되면 underflow가 된다. merge를 한 후 부모 노드를 업데이트 해준다. 삭제 후 underflow가 발생하므로 merge나 redistribute를 해야한다. merge를 할 수 없으므로 kim을 가져와서 키의 최소 기준을 맞춘다. gold를 삭제하면 최소 키의 개수 2이 안되므로 merge를 사용할 수 있다. 같은 부모를 기준으로 merge하는 것이 편하므로 .. 2020. 6. 5. [Indexing]B+ tree insertion insert할 노드가 full이면 split을 해야한다. 기존 노드가 k1 ... kn 이 있는 상황이라면 C(n/2)씩 나눈다. 나눈 노드에 대해서 부모 노드도 child 하나를 추가한다. 부모 노드의 새로운 key값은 node 2의 가장 작은 키 값이 된다. splitting non-leaf node 부모 노드도 full이면 부모 노드를 split 해야한다. 이런 상황이 root까지 올라갈 수도 있다. non-leaf node를 splitting할 때 key값 하나를 올려 보내고 node를 splitting 한다. 1. Adams를 검색하여 노드를 선택한다. 2. node가 full이기 때문에 split한다. 3. A B Ca Cr 을 나눈다. C(n/2)기준으로 나누면 2개씩 나눈다. 4. Ca를 .. 2020. 6. 5. [Indexing]B+ tree index simple index 사이즈가 커지게 되면 메인 메모리에 올리기 어려워서 비효율적이다. 그렇기 떄문에 b+ tree나 hashing을 쓰게 된다. 학생 테이블이 있을 때 학번에 대해서 검색이 자주 일어나면 미리 학번에 대한 b+ tree를 disk에 만들어두고 사용할 수 있다. 이에 대한 hash file을 만들어 두어도 된다. B tree family = B tree, B+ tree, B* tree 가장 장점이 많은 트리가 B+ tree이고 가장 널리 사용된다. insert, delete 될 때 변화가 지역적으로 발생하는 것이 장점이다. simple index의 장점은 메인 메모리에 로드해서 사용할 수 있는데 크기가 커지면 그 비용이 커진다. 따라서 B+ tree가 대안이 될 수 있다. B+ tree.. 2020. 6. 5. [Indexing]Multilevel index disk에 있는 simple index를 main memory를 올려서 사용하면 search에 대한 cost가 cpu cost이기 때문에 적다. 하지만, data file이 매우 크게 되면 simple index를 main memory에 올리기 어렵다. 그러면 구조를 바꿔서 simple index에 대한 sparse index를 만들어 main memory에 올려서 사용하면 된다. sparse index에서는 블락에 대한 가장 작은 키 값을 index 키로 해서 만들 수 있다. index update: deletion in data file dense index인 경우 data file에서 delete가 발생하면 dense index에서도 지워야 한다. sparse index인 경우 위 사진처럼 spar.. 2020. 6. 5. 이전 1 ··· 31 32 33 34 35 36 37 ··· 73 다음
