DBMS - Băm

Đối với một cấu trúc cơ sở dữ liệu khổng lồ, gần như không thể tìm kiếm tất cả các giá trị chỉ mục thông qua tất cả các cấp của nó và sau đó đến khối dữ liệu đích để lấy dữ liệu mong muốn. Hashing là một kỹ thuật hiệu quả để tính toán vị trí trực tiếp của một bản ghi dữ liệu trên đĩa mà không cần sử dụng cấu trúc chỉ mục.

Hashing sử dụng các hàm băm với các khóa tìm kiếm làm tham số để tạo địa chỉ của một bản ghi dữ liệu.

Tổ chức băm

Bucket- Tệp băm lưu trữ dữ liệu ở định dạng thùng. Xô được coi là một đơn vị chứa đựng. Một thùng thường lưu trữ một khối đĩa hoàn chỉnh, do đó có thể lưu trữ một hoặc nhiều bản ghi.
Hash Function - Một hàm băm, h, là một chức năng ánh xạ ánh xạ tất cả các bộ phím tìm kiếm Kđến địa chỉ nơi đặt hồ sơ thực tế. Nó là một chức năng từ khóa tìm kiếm đến địa chỉ nhóm.

Băm tĩnh

Trong băm tĩnh, khi giá trị khóa tìm kiếm được cung cấp, hàm băm luôn tính cùng một địa chỉ. Ví dụ, nếu hàm băm mod-4 được sử dụng, thì nó sẽ chỉ tạo ra 5 giá trị. Địa chỉ đầu ra phải luôn giống nhau cho chức năng đó. Số lượng nhóm được cung cấp không thay đổi tại mọi thời điểm.

Hoạt động

Insertion - Khi cần nhập một bản ghi bằng cách sử dụng hàm băm tĩnh, hàm băm h tính toán địa chỉ nhóm cho khóa tìm kiếm K, nơi bản ghi sẽ được lưu trữ.

Địa chỉ nhóm = h (K)
Search - Khi một bản ghi cần được truy xuất, có thể sử dụng cùng một hàm băm để truy xuất địa chỉ của thùng chứa dữ liệu.
Delete - Đây chỉ đơn giản là một tìm kiếm sau đó là một thao tác xóa.

Tràn nhóm

Tình trạng tràn thùng được gọi là collision. Đây là trạng thái nghiêm trọng đối với bất kỳ hàm băm tĩnh nào. Trong trường hợp này, có thể sử dụng chuỗi tràn.

Overflow Chaining- Khi các nhóm đầy, một nhóm mới được cấp phát cho cùng một kết quả băm và được liên kết sau nhóm trước đó. Cơ chế này được gọi làClosed Hashing.

Linear Probing- Khi một hàm băm tạo ra một địa chỉ mà tại đó dữ liệu đã được lưu trữ, thì nhóm miễn phí tiếp theo sẽ được cấp phát cho nó. Cơ chế này được gọi làOpen Hashing.

Băm động

Vấn đề với băm tĩnh là nó không mở rộng hoặc thu nhỏ động khi kích thước của cơ sở dữ liệu tăng lên hoặc thu nhỏ. Băm động cung cấp một cơ chế trong đó các nhóm dữ liệu được thêm vào và xóa một cách động và theo yêu cầu. Hàm băm động còn được gọi làextended hashing.

Hàm băm, trong băm động, được tạo ra để tạo ra một số lượng lớn các giá trị và chỉ một số ít được sử dụng ban đầu.

Cơ quan

Tiền tố của toàn bộ giá trị băm được lấy làm chỉ mục băm. Chỉ một phần của giá trị băm được sử dụng cho địa chỉ nhóm tính toán. Mỗi chỉ mục băm đều có giá trị độ sâu để biểu thị có bao nhiêu bit được sử dụng để tính toán một hàm băm. Các bit này có thể giải quyết các nhóm 2n. Khi tất cả các bit này được sử dụng - nghĩa là khi tất cả các nhóm đầy - thì giá trị độ sâu được tăng tuyến tính và hai lần các nhóm được phân bổ.

Hoạt động

Querying - Nhìn vào giá trị độ sâu của chỉ số băm và sử dụng các bit đó để tính địa chỉ thùng.
Update - Thực hiện truy vấn như trên và cập nhật dữ liệu.
Deletion - Thực hiện truy vấn để định vị dữ liệu mong muốn và xóa tương tự.
Insertion - Tính toán địa chỉ của thùng
- Nếu thùng đã đầy.
  - Thêm nhiều nhóm hơn.
  - Thêm các bit bổ sung vào giá trị băm.
  - Tính toán lại hàm băm.
- Khác
  - Thêm dữ liệu vào nhóm,
- Nếu tất cả các nhóm đã đầy, hãy thực hiện các biện pháp khắc phục sự cố băm tĩnh.

Việc băm không thuận lợi khi dữ liệu được tổ chức theo một số thứ tự và các truy vấn yêu cầu một loạt dữ liệu. Khi dữ liệu rời rạc và ngẫu nhiên, hàm băm hoạt động tốt nhất.

Các thuật toán băm có độ phức tạp cao hơn so với lập chỉ mục. Tất cả các hoạt động băm được thực hiện trong thời gian không đổi.