การแฮชใน DBMS: เทคนิคการแฮชแบบคงที่และไดนามิก
ทีมบรรณาธิการ
⚡ สรุปอย่างชาญฉลาด
การแฮชในระบบจัดการฐานข้อมูล (DBMS) เป็นเทคนิคที่คำนวณตำแหน่งบนดิสก์ของระเบียนโดยตรงจากคีย์ โดยไม่ต้องไล่ดูดัชนี ฟังก์ชันแฮชจะแมปคีย์การค้นหาไปยังกลุ่มข้อมูล และการแฮชแบบคงที่หรือแบบไดนามิกจะจัดการวิธีการขยายกลุ่มข้อมูลเหล่านั้น
การแฮชใน DBMS คืออะไร
ในระบบจัดการฐานข้อมูล (DBMS) การแฮชเป็นเทคนิคที่ใช้ในการค้นหาข้อมูลที่ต้องการบนดิสก์โดยตรงโดยไม่ต้องใช้โครงสร้างดัชนี วิธีการแฮชถูกใช้เพื่อสร้างดัชนีและเรียกค้นรายการในฐานข้อมูล เนื่องจากค้นหารายการที่ต้องการได้เร็วกว่าโดยใช้คีย์แฮชที่สั้นกว่าแทนที่จะใช้ค่าเดิม ข้อมูลจะถูกจัดเก็บในรูปแบบของบล็อกข้อมูลซึ่งที่อยู่ของบล็อกนั้นสร้างขึ้นโดยใช้ฟังก์ชันแฮช ตำแหน่งหน่วยความจำที่จัดเก็บเรคอร์ดเหล่านี้เรียกว่า DBMS บล็อกข้อมูลหรือที่เก็บข้อมูล.
ทำไมเราจึงต้องการการแฮช?
ต่อไปนี้คือสถานการณ์ในระบบจัดการฐานข้อมูล (DBMS) ที่คุณจำเป็นต้องใช้วิธีการแฮช:
- สำหรับโครงสร้างฐานข้อมูลขนาดใหญ่ การค้นหาค่าดัชนีทั้งหมดในทุกระดับและเข้าถึงบล็อกข้อมูลปลายทางเพื่อดึงข้อมูลที่ต้องการนั้นเป็นเรื่องยาก
- การแฮชถูกนำมาใช้ในการจัดทำดัชนีและเรียกค้นข้อมูลในฐานข้อมูล เนื่องจากสามารถค้นหาข้อมูลเฉพาะได้เร็วกว่าโดยใช้คีย์แฮชที่สั้นกว่าเมื่อเทียบกับค่าเดิม
- การแฮชเป็นวิธีการที่เหมาะสมในการคำนวณตำแหน่งโดยตรงของระเบียนข้อมูลบนดิสก์โดยไม่ต้องใช้โครงสร้างดัชนี
- นอกจากนี้ยังเป็นเทคนิคที่เป็นประโยชน์ในการใช้พจนานุกรมอีกด้วย
คำศัพท์ที่สำคัญในการแฮชชิง
ต่อไปนี้เป็นคำศัพท์สำคัญที่ใช้ในการแฮช:
- ถังเก็บข้อมูล: หน่วยเก็บข้อมูล (Data buckets) คือตำแหน่งในหน่วยความจำที่ใช้จัดเก็บระเบียนข้อมูล เรียกอีกอย่างว่าหน่วยจัดเก็บข้อมูล
- คีย์: a คีย์ DBMS คือคุณลักษณะหรือชุดของคุณลักษณะที่ช่วยให้คุณระบุแถว (ทูเปิล) ในความสัมพันธ์ (ตาราง) ได้
- ฟังก์ชันแฮช: แผนที่ping ฟังก์ชันที่จับคู่ชุดคีย์การค้นหาทั้งหมดกับที่อยู่ซึ่งจัดเก็บระเบียนจริงไว้
- การวัดเชิงเส้น: กำหนดช่วงเวลาคงที่ระหว่างการตรวจสอบแต่ละครั้ง ในวิธีนี้ จะใช้บล็อกข้อมูลที่ว่างอยู่ถัดไปเพื่อบันทึกข้อมูลใหม่ แทนที่จะเขียนทับข้อมูลเก่า
- การทดสอบแบบกำลังสอง: ช่วยกำหนดที่อยู่บัคเก็ตใหม่โดยการเพิ่มผลลัพธ์ต่อเนื่องของพหุนามกำลังสองเข้ากับค่าเริ่มต้นที่ได้จากการคำนวณครั้งแรก
- ดัชนีแฮช: ที่อยู่ของบล็อกข้อมูล ฟังก์ชันแฮชอาจเป็นฟังก์ชันทางคณิตศาสตร์อย่างง่ายหรือซับซ้อนก็ได้
- Double การแฮช: วิธีการที่ใช้ในตารางแฮชเพื่อแก้ไขปัญหาการชนกันของค่าแฮชโดยการใช้ฟังก์ชันแฮชตัวที่สอง
- ถังล้น: สภาวะที่บัคเก็ตล้นเรียกว่าการชนกัน (collision) ซึ่งเป็นสภาวะร้ายแรงสำหรับฟังก์ชันแฮชแบบคงที่ใดๆ
ประเภทของเทคนิคการแฮช
โดยหลักแล้ว เทคนิคการแฮชในระบบจัดการฐานข้อมูลมีอยู่ 2 ประเภท:
- การแฮชแบบคงที่
- การแฮชแบบไดนามิก
ทั้งสองแบบแตกต่างกันหลักๆ ตรงที่จำนวนถังเก็บน้ำนั้นคงที่หรือไม่ ซึ่งจะอธิบายในสองส่วนถัดไป
การแฮชแบบคงที่
ในการแฮชแบบคงที่ ที่อยู่ของกลุ่มข้อมูลที่ได้จะคงเดิมเสมอ
ดังนั้น หากคุณสร้างที่อยู่สำหรับตัวอย่างเช่น รหัสนักเรียน = 10 โดยใช้ฟังก์ชันแฮช ม็อด(3)ที่อยู่บัคเก็ตผลลัพธ์จะเป็นเสมอ 1ดังนั้นคุณจะไม่เห็นการเปลี่ยนแปลงใดๆ ในที่อยู่ของบัคเก็ต
ดังนั้น ในวิธีการแฮชแบบคงที่ จำนวนบัคเก็ตข้อมูลในหน่วยความจำจึงคงที่เสมอ
ฟังก์ชันแฮชแบบคงที่
- การเพิ่มข้อมูล: เมื่อต้องการแทรกข้อมูลใหม่ลงในตาราง คุณจะต้องสร้างที่อยู่สำหรับข้อมูลนั้นโดยใช้คีย์แฮช เมื่อสร้างที่อยู่แล้ว ข้อมูลจะถูกจัดเก็บไว้ในตำแหน่งนั้น
- ค้นหา: เมื่อต้องการเรียกดูข้อมูล ระบบจะใช้ฟังก์ชันแฮชเดียวกันในการเรียกดูที่อยู่ของบัคเก็ตที่เก็บข้อมูลนั้นไว้
- ลบข้อมูล: การใช้ฟังก์ชันแฮช คุณจะต้องดึงข้อมูลที่ต้องการลบออกมาก่อน จากนั้นจึงลบข้อมูลนั้นออกจากตำแหน่งในหน่วยความจำ
การแฮชแบบคงที่ยังแบ่งออกเป็น:
- เปิดการแฮช
- การแฮชแบบปิด
เปิดการแฮช
ในวิธีการแฮชแบบเปิด แทนที่จะเขียนทับเรคอร์ดเก่า จะใช้บล็อกข้อมูลที่ว่างอยู่ถัดไปเพื่อสร้างเรคอร์ดใหม่ วิธีนี้เรียกอีกอย่างว่าการค้นหาเชิงเส้น (linear probing)
ตัวอย่างเช่น A2 คือเรคอร์ดใหม่ที่คุณต้องการแทรก ฟังก์ชันแฮชสร้างที่อยู่ 222 แต่ที่อยู่นั้นถูกใช้โดยค่าอื่นอยู่แล้ว ดังนั้นระบบจึงมองหาบัคเก็ตข้อมูลถัดไปคือ 501 และกำหนด A2 ให้กับบัคเก็ตนั้น
การแฮชแบบปิด
ในวิธีการแฮชแบบปิด เมื่อบัคเก็ตเต็ม ระบบจะจัดสรรบัคเก็ตใหม่สำหรับแฮชเดียวกัน และผลลัพธ์จะถูกเชื่อมโยงต่อจากผลลัพธ์ก่อนหน้า
การแฮชแบบไดนามิก
การแฮชแบบไดนามิกเป็นกลไกที่ช่วยให้สามารถเพิ่มและลบกลุ่มข้อมูลได้อย่างไดนามิกและตามความต้องการ ในวิธีการแฮชแบบนี้ ฟังก์ชันแฮชจะช่วยให้คุณสร้างค่าจำนวนมาก และโครงสร้างจะขยายหรือหดตัวตามข้อมูล ทำให้เหมาะอย่างยิ่งสำหรับตารางที่มีขนาดไม่สามารถคาดการณ์ล่วงหน้าได้ ซึ่งการแฮชแบบคงที่อาจทำให้สิ้นเปลืองพื้นที่หรือเกิดการล้นได้
ความแตกต่างระหว่างการจัดทำดัชนีแบบเรียงลำดับและการแฮช
ต่อไปนี้คือความแตกต่างที่สำคัญระหว่างการทำดัชนีและการแฮช:
| พารามิเตอร์ | การจัดทำดัชนีตามลำดับ | hashing |
|---|---|---|
| การจัดเก็บที่อยู่ | ที่อยู่ในหน่วยความจำจะถูกจัดเรียงตามค่าคีย์ที่เรียกว่าคีย์หลัก | ที่อยู่จะถูกสร้างขึ้นเสมอโดยใช้ฟังก์ชันแฮชกับค่าคีย์ |
| ประสิทธิภาพ | จำนวนครั้งในการจัดเก็บอาจลดลงเมื่อข้อมูลเพิ่มขึ้น เนื่องจากข้อมูลถูกจัดเก็บในรูปแบบเรียงลำดับ และการเพิ่ม ลบ หรืออัปเดตแต่ละครั้งจะทำให้ข้อมูลเรียงลำดับใหม่ | ประสิทธิภาพจะดีที่สุดเมื่อมีการเพิ่มและลบข้อมูลอย่างต่อเนื่อง สำหรับฐานข้อมูลขนาดใหญ่ การบำรุงรักษาไฟล์แฮชจะมีค่าใช้จ่ายสูงขึ้น |
| ใช้สำหรับการ | เหมาะสำหรับการดึงข้อมูลในช่วงที่กำหนด | เหมาะอย่างยิ่งสำหรับการค้นหาข้อมูลเฉพาะโดยใช้คีย์การค้นหา และจะทำงานได้ดีก็ต่อเมื่อใช้ฟังก์ชันแฮชกับคีย์การค้นหาเท่านั้น |
| การจัดการหน่วยความจำ | บล็อกข้อมูลที่ไม่ได้ใช้งานจำนวนมากเกิดขึ้นจากการดำเนินการลบและอัปเดต และไม่สามารถนำกลับมาใช้ใหม่ได้ ดังนั้นจึงจำเป็นต้องมีการบำรุงรักษาเป็นประจำ | ในการแฮชแบบคงที่และแบบไดนามิก หน่วยความจำจะได้รับการจัดการเสมอ และปัญหาหน่วยความจำล้นจะถูกจัดการเพื่อขยายขีดความสามารถของการแฮชแบบคงที่ |
โดยสรุปคือ เลือกตามลำดับ การจัดทำดัชนี สำหรับการค้นหาแบบช่วง และการแฮชสำหรับการค้นหาแบบตรงกันทุกประการบนคีย์
การชนกันคืออะไร?
การชนกันของแฮช (Hash collision) คือสถานะที่ค่าแฮชที่ได้จากข้อมูลสองรายการขึ้นไปในชุดข้อมูลนั้น จับคู่กับตำแหน่งเดียวกันอย่างไม่ถูกต้อง ตารางแฮช.
วิธีรับมือกับปัญหาการชนกันของแฮช
มีสองเทคนิคที่คุณสามารถใช้เพื่อหลีกเลี่ยงการชนกันของค่าแฮช:
- สรุปโดยย่อ: วิธีการนี้จะเรียกใช้ฟังก์ชันแฮชรอง ซึ่งจะถูกนำไปใช้อย่างต่อเนื่องจนกว่าจะพบช่องว่างที่สามารถบันทึกข้อมูลได้
- การผูกมัด: วิธีการเชื่อมโยงแบบลูกโซ่จะสร้างรายการเชื่อมโยงของรายการที่มีคีย์ซึ่งมีค่าแฮชเดียวกัน วิธีนี้ต้องการฟิลด์เชื่อมโยงเพิ่มเติมที่ตำแหน่งตารางแต่ละตำแหน่ง
