การแฮชใน DBMS: เทคนิคการแฮชแบบคงที่และไดนามิก

การแฮชใน DBMS คืออะไร

ใน DBMS การแฮชเป็นเทคนิคในการค้นหาตำแหน่งของข้อมูลที่ต้องการบนดิสก์โดยตรงโดยไม่ต้องใช้โครงสร้างดัชนี วิธีการแฮชใช้เพื่อสร้างดัชนีและดึงข้อมูลรายการในฐานข้อมูลเนื่องจากจะค้นหารายการนั้นได้เร็วกว่าโดยใช้คีย์แฮชที่สั้นกว่าแทนที่จะใช้ค่าดั้งเดิม ข้อมูลจะถูกจัดเก็บในรูปแบบของบล็อกข้อมูลซึ่งมีการสร้างที่อยู่โดยใช้ฟังก์ชันแฮชในตำแหน่งหน่วยความจำซึ่งบันทึกเหล่านี้ถูกจัดเก็บเรียกว่า บล็อกข้อมูลหรือที่เก็บข้อมูล.

ทำไมเราถึงต้องมีการแฮช?

ต่อไปนี้คือสถานการณ์ใน DBMS ที่คุณต้องใช้วิธีการ Hashing:

สำหรับโครงสร้างฐานข้อมูลขนาดใหญ่ การค้นหาค่าดัชนีทั้งหมดในทุกระดับเป็นเรื่องยาก จากนั้นคุณจะต้องไปถึงบล็อกข้อมูลปลายทางเพื่อรับข้อมูลที่ต้องการ
วิธีการแฮชใช้เพื่อสร้างดัชนีและดึงข้อมูลรายการในฐานข้อมูลเนื่องจากจะค้นหารายการนั้นได้เร็วกว่าโดยใช้คีย์แฮชที่สั้นกว่าแทนที่จะใช้ค่าดั้งเดิม
การแฮชเป็นวิธีการที่เหมาะสมที่สุดในการคำนวณตำแหน่งโดยตรงของบันทึกข้อมูลบนดิสก์โดยไม่ต้องใช้โครงสร้างดัชนี
นอกจากนี้ยังเป็นเทคนิคที่เป็นประโยชน์ในการใช้พจนานุกรมอีกด้วย

คำศัพท์ที่สำคัญในการแฮชชิง

ต่อไปนี้เป็นคำศัพท์สำคัญที่ใช้ใน Hashing:

ที่เก็บข้อมูล – ที่เก็บข้อมูลคือตำแหน่งหน่วยความจำที่บันทึกข้อมูลไว้ เป็นที่รู้จักกันว่าหน่วยเก็บข้อมูล
คีย์: คีย์ DBMS เป็นคุณลักษณะหรือชุดของคุณลักษณะที่ช่วยให้คุณระบุแถว (tuple) ในความสัมพันธ์ (ตาราง) ซึ่งจะทำให้คุณสามารถค้นหาความสัมพันธ์ระหว่างสองตารางได้
ฟังก์ชันแฮช: ฟังก์ชันแฮช คือฟังก์ชันการแมปที่แมปชุดคีย์ค้นหาทั้งหมดไปยังที่อยู่ที่วางบันทึกจริง
การตรวจสอบเชิงเส้น – การตรวจวัดเชิงเส้นเป็นช่วงเวลาที่คงที่ระหว่างโพรบ ในวิธีนี้ บล็อกข้อมูลถัดไปที่มีอยู่จะถูกนำมาใช้เพื่อป้อนเรกคอร์ดใหม่ แทนที่จะเขียนทับบนเรกคอร์ดเก่า
การตรวจสอบกำลังสอง– ช่วยให้คุณกำหนดที่อยู่บัคเก็ตใหม่ ช่วยให้คุณเพิ่มช่วงเวลาระหว่างโพรบได้โดยการเพิ่มเอาต์พุตต่อเนื่องของพหุนามกำลังสองเข้ากับค่าเริ่มต้นที่กำหนดโดยการคำนวณดั้งเดิม
ดัชนีแฮช – เป็นที่อยู่ของบล็อกข้อมูล ฟังก์ชันแฮชอาจเป็นฟังก์ชันทางคณิตศาสตร์แบบง่ายไปจนถึงฟังก์ชันทางคณิตศาสตร์ที่ซับซ้อน
Double hashing -Double การแฮชเป็นวิธีการเขียนโปรแกรมคอมพิวเตอร์ที่ใช้ในตารางแฮชเพื่อแก้ไขปัญหาการชนกัน
ถังล้น: สภาวะของบัคเก็ตโอเวอร์โฟลว์เรียกว่าการชนกัน นี่เป็นระยะร้ายแรงสำหรับการทำงานแบบคงที่

ประเภทของเทคนิคการแฮช

ส่วนใหญ่มีวิธี/เทคนิคการแฮช SQL สองประเภท:

การแฮชแบบคงที่
การแฮชแบบไดนามิก

การแฮชแบบคงที่

ในการแฮชแบบคงที่ ที่อยู่ที่เก็บข้อมูลผลลัพธ์จะยังคงเหมือนเดิมเสมอ

ดังนั้นหากคุณสร้างที่อยู่เพื่อพูด รหัสนักเรียน = 10 ใช้ฟังก์ชันแฮช ม็อด(3)ที่อยู่บัคเก็ตผลลัพธ์จะเป็นเสมอ 1- ดังนั้น คุณจะไม่เห็นการเปลี่ยนแปลงใดๆ ในที่อยู่บัคเก็ต

ดังนั้นในวิธีการแฮชแบบคงที่นี้ จำนวนที่เก็บข้อมูลในหน่วยความจำจึงคงที่เสมอ

ฟังก์ชันแฮชแบบคงที่

การแทรกบันทึก: เมื่อจำเป็นต้องแทรกบันทึกใหม่ลงในตาราง คุณสามารถสร้างที่อยู่สำหรับบันทึกใหม่ได้โดยใช้แฮชคีย์ เมื่อสร้างที่อยู่แล้ว บันทึกจะถูกจัดเก็บไว้ในตำแหน่งนั้นโดยอัตโนมัติ
ค้นหา: เมื่อคุณต้องการดึงข้อมูลบันทึก ฟังก์ชันแฮชเดียวกันควรจะเป็นประโยชน์ในการดึงข้อมูลที่อยู่ของบัคเก็ตที่ควรจัดเก็บข้อมูล
ลบเรกคอร์ด: เมื่อใช้ฟังก์ชันแฮช คุณสามารถดึงข้อมูลบันทึกที่คุณต้องการลบได้ก่อน จากนั้นคุณสามารถลบบันทึกสำหรับที่อยู่นั้นในหน่วยความจำได้

การแฮชแบบคงที่ยังแบ่งออกเป็น

เปิดการแฮช
ปิดการแฮช

เปิดการแฮช

ในวิธีการเปิดแฮช แทนที่จะเขียนทับอันเก่า บล็อกข้อมูลถัดไปที่มีอยู่จะถูกนำมาใช้เพื่อป้อนบันทึกใหม่ วิธีการนี้เรียกอีกอย่างว่าการตรวจสอบเชิงเส้น

ตัวอย่างเช่น A2 คือระเบียนใหม่ที่คุณต้องการแทรก ฟังก์ชันแฮชสร้างที่อยู่เป็น 222 แต่ค่าอื่นบางส่วนถูกครอบครองแล้ว นั่นเป็นสาเหตุที่ระบบค้นหาที่เก็บข้อมูลถัดไป 501 และกำหนด A2 ให้กับมัน

ปิดการแฮช

ในวิธีการปิดแฮช เมื่อบัคเก็ตเต็ม บัคเก็ตใหม่จะถูกจัดสรรสำหรับแฮชเดียวกัน และผลลัพธ์จะถูกเชื่อมโยงหลังจากแฮชก่อนหน้า

การแฮชแบบไดนามิก

การแฮชแบบไดนามิกเสนอกลไกในการเพิ่มและลบที่เก็บข้อมูลแบบไดนามิกและตามความต้องการ ในการแฮชนี้ ฟังก์ชันแฮชจะช่วยคุณสร้างค่าจำนวนมาก

ความแตกต่างระหว่างการจัดทำดัชนีที่สั่งและการแฮช

ด้านล่างนี้คือข้อแตกต่างที่สำคัญระหว่างการจัดทำดัชนีและการแฮช

พารามิเตอร์	การจัดทำดัชนีคำสั่งซื้อ	hashing
การจัดเก็บที่อยู่	ที่อยู่ในหน่วยความจำจะถูกจัดเรียงตามค่าคีย์ที่เรียกว่าคีย์หลัก	ที่อยู่จะถูกสร้างขึ้นเสมอโดยใช้ฟังก์ชันแฮชกับค่าคีย์
ประสิทธิภาพ	อาจลดลงได้เมื่อข้อมูลในไฟล์แฮชเพิ่มขึ้น เนื่องจากจะจัดเก็บข้อมูลในรูปแบบเรียงลำดับเมื่อมีการดำเนินการใดๆ (แทรก/ลบ/อัปเดต) ซึ่งจะทำให้ประสิทธิภาพลดลง	ประสิทธิภาพของการแฮชจะดีที่สุดเมื่อมีการเพิ่มและลบข้อมูลอย่างต่อเนื่อง อย่างไรก็ตาม เมื่อฐานข้อมูลมีขนาดใหญ่ การจัดระเบียบไฟล์แฮชและการบำรุงรักษาจะมีต้นทุนสูงกว่า
ใช้สำหรับการ	แนะนำให้ใช้สำหรับการดึงข้อมูลเป็นช่วง ซึ่งหมายความว่าเมื่อใดก็ตามที่มีการดึงข้อมูลสำหรับช่วงใดช่วงหนึ่ง วิธีนี้ถือเป็นตัวเลือกที่เหมาะสมที่สุด	นี่เป็นวิธีการที่เหมาะสมที่สุดเมื่อคุณต้องการดึงข้อมูลบันทึกเฉพาะตามคีย์การค้นหา อย่างไรก็ตาม จะทำงานได้ดีเมื่อฟังก์ชันแฮชอยู่บนคีย์ค้นหาเท่านั้น
การจัดการหน่วยความจำ	จะมีบล็อกข้อมูลที่ไม่ได้ใช้งานจำนวนมากเนื่องจากการดำเนินการลบ/อัปเดต บล็อกข้อมูลเหล่านี้ไม่สามารถปล่อยให้กลับมาใช้ซ้ำได้ ดังนั้นจึงต้องบำรุงรักษาหน่วยความจำเป็นประจำ	ในวิธีการแฮชแบบสแตติกและไดนามิก หน่วยความจำจะได้รับการจัดการอยู่เสมอ นอกจากนี้ บัคเก็ตโอเวอร์โฟลว์ยังได้รับการจัดการอย่างสมบูรณ์แบบเพื่อขยายการแฮชแบบคงที่

การชนกันคืออะไร?

การชนกันของแฮชคือสถานะที่แฮชผลลัพธ์จากข้อมูลตั้งแต่สองข้อมูลขึ้นไปในชุดข้อมูล แมปสถานที่เดียวกันในชุดข้อมูลอย่างไม่ถูกต้อง ตารางแฮช.

จะจัดการกับ Hashing Collision ได้อย่างไร?

มีสองเทคนิคที่คุณสามารถใช้เพื่อหลีกเลี่ยงการชนกันของแฮช:

รีแฮช: วิธีการนี้จะเรียกใช้ฟังก์ชันแฮชรอง ซึ่งจะใช้อย่างต่อเนื่องจนกว่าจะพบช่องที่ว่าง ซึ่งควรวางบันทึก
ผูกมัด: วิธีการผูกมัดจะสร้างรายการที่เชื่อมโยงของรายการที่มีคีย์แฮชเป็นค่าเดียวกัน วิธีการนี้จำเป็นต้องมีฟิลด์ลิงก์เพิ่มเติมไปยังแต่ละตำแหน่งตาราง

สรุป

In DBMSการแฮชเป็นเทคนิคในการค้นหาตำแหน่งของข้อมูลที่ต้องการบนดิสก์โดยตรงโดยไม่ต้องใช้โครงสร้างดัชนี
วิธีการแฮชใช้เพื่อสร้างดัชนีและดึงข้อมูลรายการในฐานข้อมูลเนื่องจากจะค้นหารายการนั้นได้เร็วกว่าโดยใช้คีย์แฮชที่สั้นกว่าแทนที่จะใช้ค่าดั้งเดิม
ที่เก็บข้อมูล, คีย์, ฟังก์ชันแฮช, การตรวจสอบเชิงเส้น, การตรวจสอบกำลังสอง, ดัชนีแฮช, Double Hashing, Bucket Overflow เป็นคำศัพท์สำคัญที่ใช้ในการแฮช
วิธีการแฮชสองประเภทคือ 1) การแฮชแบบคงที่ 2) การแฮชแบบไดนามิก
ในการแฮชแบบคงที่ ที่อยู่ที่เก็บข้อมูลผลลัพธ์จะยังคงเหมือนเดิมเสมอ
การแฮชแบบไดนามิกเสนอกลไกในการเพิ่มและลบที่เก็บข้อมูลแบบไดนามิกและตามความต้องการ
ตามลำดับ ที่อยู่การจัดทำดัชนีในหน่วยความจำจะถูกจัดเรียงตามค่าวิกฤต ในขณะที่ที่อยู่การแฮชจะถูกสร้างขึ้นเสมอโดยใช้ฟังก์ชันแฮชกับค่าคีย์
การชนกันของแฮชคือสถานะที่แฮชผลลัพธ์จากข้อมูลตั้งแต่สองข้อมูลขึ้นไปในชุดข้อมูล แมปตำแหน่งเดียวกันในตารางแฮชอย่างไม่ถูกต้อง
การแฮชซ้ำและการผูกมัดเป็นสองวิธีที่ช่วยให้คุณหลีกเลี่ยงการชนกันของแฮช