컴퓨터공학/데이터베이스(database)45 [Indexing] Non-unique search key, b+ tree variation, b tree 중복된 key 값이 존재한다면 어떻게 해야할까? 이전에 simple index에서 bucket을 살펴보았다. leaf노드와 record 중간에 bucket을 두는 것을 고려할 수 있다. 아니면, 중복되는 키 값을 허용할 수도 있다. k1 2020. 6. 6. [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. 이전 1 2 3 4 5 6 7 ··· 12 다음
