DB 자료 줄이기

DB에 저장할 자료의 용량을 줄이기 위해 고민 중이다.

1. Huffman Compress, zip 등으로 압축한다.
2. decoding은 안되지만 identical만 확인하면 된다면 digest function을 써도 된다. - MD5 등..
3. NFS를 사용해 network으로 mount해서 사용하면 복사본의 갯수가 줄어든다.
   (성능은 나빠질 수도 있다.)
4. 긴 string으로 구성된 field는 id를 발급해서 string을 대신한다.
5. data structure design을 다시 한다.
6. DB를 reorganize하면 B+ tree의 index가 최적화되어 속도로 빨라지고 용량도 줄어딘다.

----------------------
hash collision problem
2^30개의 key를 DB에 저장할 때
key의 길이가 너무 길어 용량을 줄이기 위해
hash function을 사용하는 방법을 검토하려고 한다.
key의 본래값은 중요하지 않고 uniqueness만이 중요하기 때문에
md5 같은 digest function을 사용한다고 하자.
(I/O를 줄이는 대신 CPU 사용량이 증가하는 문제도 있다.)

md5의 결과의 경우의 수는 2^128(128bits)인데.
그렇다면 collision이 발생할 확률은 얼마일까?
birthday problem(algorithm 교재) 등에서 다루어 지는 문제인데.
http://mathworld.wolfram.com/BirthdayProblem.html
확률이 얼마 이하라면 사용가능할까?
2^128이 너무 작은 숫자라면 SHA1등 더 개선된 digest function을 사용하여
2^512(512bits) 정도로 만들면 어떨까?

이런 복잡한 계산을 피할 수 있는 compression algorithm을 쓰는 것은 어떨까?
compression algorithm(huffman code, LZ 등..)을 쓰면
길이는 hash function처럼 일정하지 않고 variable length 지만
collision free 함을 완벽하게 보장할 수가 있다