Băm trong DBMS: Kỹ thuật băm tĩnh và động

Tại sao chúng ta cần Hashing?

Dưới đây là các tình huống trong DBMS mà bạn cần áp dụng phương pháp Băm:

• Đối với cấu trúc cơ sở dữ liệu khổng lồ, thật khó để tìm kiếm tất cả các giá trị chỉ mục ở tất cả các cấp của nó và sau đó bạn cần tiếp cận khối dữ liệu đích để có được dữ liệu mong muốn.
• Phương pháp băm được sử dụng để lập chỉ mục và truy xuất các mục trong cơ sở dữ liệu vì việc tìm kiếm mục cụ thể đó bằng cách sử dụng khóa băm ngắn hơn thay vì sử dụng giá trị ban đầu của nó sẽ nhanh hơn.
• Băm là một phương pháp lý tưởng để tính toán vị trí trực tiếp của bản ghi dữ liệu trên đĩa mà không cần sử dụng cấu trúc chỉ mục.
• Nó cũng là một kỹ thuật hữu ích để thực hiện từ điển.

Các thuật ngữ quan trọng trong băm

Dưới đây là các thuật ngữ quan trọng được sử dụng trong Hashing:

• Nhóm dữ liệu – Thùng dữ liệu là vị trí bộ nhớ nơi lưu trữ các bản ghi. Nó còn được gọi là Đơn vị lưu trữ.
• Key: A Khóa DBMS là một thuộc tính hoặc tập hợp thuộc tính giúp bạn xác định một hàng (bộ) trong một mối quan hệ (bảng). Điều này cho phép bạn tìm thấy mối quan hệ giữa hai bảng.
• Hàm băm: Hàm băm, là hàm ánh xạ ánh xạ tất cả tập hợp khóa tìm kiếm tới địa chỉ nơi đặt bản ghi thực tế.
• Thăm dò tuyến tính – Thăm dò tuyến tính là khoảng cách cố định giữa các lần thăm dò. Trong phương pháp này, khối dữ liệu có sẵn tiếp theo được sử dụng để nhập bản ghi mới, thay vì ghi đè lên bản ghi cũ.
• thăm dò bậc hai– Nó giúp bạn xác định địa chỉ nhóm mới. Nó giúp bạn thêm Khoảng thời gian giữa các đầu dò bằng cách cộng đầu ra liên tiếp của đa thức bậc hai vào giá trị bắt đầu được đưa ra bởi phép tính ban đầu.
• Chỉ số băm – Đây là địa chỉ của khối dữ liệu. Hàm băm có thể là một hàm toán học đơn giản hoặc thậm chí là một hàm toán học phức tạp.
• Double Băm –Double băm là một phương pháp lập trình máy tính được sử dụng trong bảng băm để giải quyết các vấn đề xung đột.
• Tràn thùng: Tình trạng tràn thùng gọi là va chạm. Đây là một giai đoạn quan trọng đối với bất kỳ hoạt động tĩnh nào.

Các loại kỹ thuật băm

Chủ yếu có hai loại phương pháp/kỹ thuật băm SQL:

1. Băm tĩnh
2. Băm động

băm tĩnh

Trong băm tĩnh, địa chỉ nhóm dữ liệu kết quả sẽ luôn giữ nguyên.

Vì vậy, nếu bạn tạo một địa chỉ chẳng hạn Sinh viên_ID = 10 sử dụng hàm băm mod(3), địa chỉ nhóm kết quả sẽ luôn là 1. Vì vậy, bạn sẽ không thấy bất kỳ thay đổi nào trong địa chỉ nhóm.

Do đó, trong phương pháp băm tĩnh này, số lượng nhóm dữ liệu trong bộ nhớ luôn không đổi.

Hàm băm tĩnh

• Chèn một bản ghi: Khi một bản ghi mới cần được chèn vào bảng, bạn có thể tạo địa chỉ cho bản ghi mới bằng khóa băm của bản ghi đó. Khi địa chỉ được tạo, bản ghi sẽ tự động được lưu trữ ở vị trí đó.
• Tìm kiếm: Khi bạn cần truy xuất bản ghi, hàm băm tương tự sẽ hữu ích để truy xuất địa chỉ của nhóm nơi lưu trữ dữ liệu.
• Xóa bản ghi: Sử dụng hàm băm, trước tiên bạn có thể tìm nạp bản ghi bạn muốn xóa. Sau đó, bạn có thể xóa bản ghi cho địa chỉ đó trong bộ nhớ.

Băm tĩnh được chia thành

1. Băm mở
2. Đóng băm.

Băm mở

Trong phương pháp băm mở, thay vì ghi đè khối dữ liệu cũ hơn, khối dữ liệu có sẵn tiếp theo được sử dụng để nhập bản ghi mới. Phương pháp này còn được gọi là thăm dò tuyến tính.

Ví dụ: A2 là bản ghi mới mà bạn muốn chèn. Hàm băm tạo địa chỉ là 222. Nhưng nó đã bị chiếm bởi một số giá trị khác. Đó là lý do tại sao hệ thống tìm kiếm nhóm dữ liệu tiếp theo 501 và gán A2 cho nó.

Đóng băm

Trong phương pháp băm đóng, khi các nhóm đầy, một nhóm mới sẽ được phân bổ cho cùng một hàm băm và kết quả được liên kết sau nhóm trước đó.

Băm động

Băm động cung cấp một cơ chế trong đó các nhóm dữ liệu được thêm và xóa một cách linh hoạt và theo yêu cầu. Trong phép băm này, hàm băm giúp bạn tạo ra một số lượng lớn các giá trị.

Sự khác biệt giữa lập chỉ mục theo thứ tự và băm

Dưới đây là những khác biệt chính giữa Lập chỉ mục và Băm

Va chạm là gì?

Xung đột băm là trạng thái khi băm kết quả từ hai hoặc nhiều dữ liệu trong tập dữ liệu, ánh xạ sai cùng một vị trí trong bảng băm.

Làm thế nào để đối phó với va chạm Hashing?

Có hai kỹ thuật bạn có thể sử dụng để tránh xung đột hàm băm:

1. Làm lại: Phương thức này gọi hàm băm thứ cấp, được áp dụng liên tục cho đến khi tìm thấy một ô trống, nơi cần đặt bản ghi.
2. Xâu chuỗi: Phương pháp xâu chuỗi xây dựng một Danh sách liên kết gồm các mục có khóa được băm thành cùng một giá trị. Phương pháp này yêu cầu một trường liên kết bổ sung cho từng vị trí trong bảng.

Tổng kết

• In DBMS, băm là một kỹ thuật tìm kiếm trực tiếp vị trí của dữ liệu mong muốn trên đĩa mà không cần sử dụng cấu trúc chỉ mục.
• Phương pháp băm được sử dụng để lập chỉ mục và truy xuất các mục trong cơ sở dữ liệu vì việc tìm kiếm mục cụ thể đó bằng cách sử dụng khóa băm ngắn hơn thay vì sử dụng giá trị ban đầu của nó sẽ nhanh hơn.
• Nhóm dữ liệu, Khóa, Hàm băm, Thăm dò tuyến tính, Thăm dò bậc hai, Chỉ số băm, Double Băm, Tràn thùng là những thuật ngữ quan trọng được sử dụng trong băm
• Hai loại phương pháp băm là 1) băm tĩnh 2) băm động
• Trong băm tĩnh, địa chỉ nhóm dữ liệu kết quả sẽ luôn giữ nguyên.
• Băm động cung cấp một cơ chế trong đó các nhóm dữ liệu được thêm và xóa một cách linh hoạt và theo yêu cầu.
• Theo thứ tự, các địa chỉ lập chỉ mục trong bộ nhớ được sắp xếp theo một giá trị quan trọng trong khi các địa chỉ băm luôn được tạo bằng cách sử dụng hàm băm trên giá trị khóa.
• Xung đột băm là trạng thái khi băm kết quả từ hai hoặc nhiều dữ liệu trong tập dữ liệu, ánh xạ sai cùng một vị trí trong bảng băm.
• Phục hồi và xâu chuỗi là hai phương pháp giúp bạn tránh xung đột băm.