ซีดีบี (ซอฟต์แวร์)

cdbซึ่งย่อมาจาก "constant database" หมายถึงทั้งไลบรารีและรูปแบบข้อมูลที่สร้างโดยDaniel J. Bernstein cdb ทำงานเหมือนอาร์เรย์แบบเชื่อมโยง บนดิสก์ โดยแมปคีย์กับค่า และอนุญาตให้จัดเก็บหลายค่าสำหรับคีย์เดียวได้ ฐานข้อมูลแบบคงที่อนุญาตให้ดำเนินการได้เพียงสองอย่าง คือ การสร้างและการอ่าน การดำเนินการทั้งสองได้รับการออกแบบให้รวดเร็วและเชื่อถือได้สูง เนื่องจากฐานข้อมูลไม่เปลี่ยนแปลงขณะใช้งาน กระบวนการหลายกระบวนการจึงสามารถเข้าถึงฐานข้อมูลเดียวได้โดยไม่ต้องล็อก นอกจากนี้ เนื่องจากทุกการแก้ไขจะสร้างฐานข้อมูลใหม่ขึ้นมาแทนที่ จึงสามารถใช้ประโยชน์จากความหมายของระบบไฟล์ UNIX เพื่อรับประกันความน่าเชื่อถือได้

ตำแหน่งบันทึก ความยาวคีย์และค่า และค่าแฮชเป็นปริมาณ 32 บิต ดังนั้นจึงต้องพอดีกับ 4 กิกะไบต์^{[ 1 ]} cdbถูกใช้โดยdjbdns , fastforward , mess822 , qmailและucspi-tcpเพื่อให้การเข้าถึงข้อมูลที่มีประสิทธิภาพสูง เชื่อถือได้ และเรียบง่าย

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

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

สำหรับการค้นหาคีย์ที่มีหลายค่า สามารถค้นหาค่าเพิ่มเติมได้โดยการเริ่มการค้นหาใหม่ในช่องถัดไป

ตัวเลขทั้งหมด—ทั้งค่าออฟเซ็ต ความยาว และค่าแฮช—เป็นจำนวนเต็ม 32 บิต ที่ไม่ติดลบ จัดเก็บใน รูปแบบ little endianคีย์และข้อมูลถือเป็นสตริง ไบต์ที่ไม่สามารถตีความได้ และไม่จำเป็นต้องได้รับการจัดการเป็นพิเศษ

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

ค่าแฮชเป็นจำนวนเต็ม 32 บิตที่ไม่มีเครื่องหมาย และเริ่มต้นด้วยค่า 5381 สำหรับแต่ละไบต์ของคีย์ ค่าแฮชปัจจุบันจะถูกคูณด้วย 33 จากนั้น ทำการ XORกับไบต์ปัจจุบันของคีย์ บิตส่วนเกินจะถูกทิ้งไป ช่องและตารางถูกคำนวณอย่างง่ายจากค่าแฮช ตารางเป้าหมายคือบิตต่ำสุดแปดบิตของค่าแฮช (เช่น ค่าแฮชหารด้วย 256) และช่องภายในตารางคือบิตที่เหลือของค่าแฮชหารด้วยความยาวของตาราง (เช่น ค่าแฮชหารด้วย 256 หารด้วยความยาวของตาราง)

รหัสไลบรารี cdb อย่างเป็นทางการเป็นสาธารณสมบัติ : ไฟล์ต้นฉบับแต่ละไฟล์ถูกทำเครื่องหมายไว้เช่นนั้น และยังมีอยู่ใน แพ็คเกจ djbdns ที่เป็นสาธารณสมบัติ ด้วย อย่างไรก็ตาม ส่วนที่เหลือของแพ็คเกจ cdb เคยเป็นซอฟต์แวร์ที่ไม่มีลิขสิทธิ์ซึ่งหมายความว่าต้องแจกจ่ายตามต้นฉบับทุกประการ การอนุญาตใช้งานที่ไม่ธรรมดาและความเรียบง่ายของรูปแบบได้กระตุ้นให้ผู้อื่นนำไลบรารีมาเขียนใหม่และเผยแพร่ภายใต้เงื่อนไขทั่วไปมากขึ้น เช่น ไลบรารี TinyCDB ของ Michael Tokarev ซึ่งมีให้ใช้งานภายใต้สาธารณสมบัติ^{[ 2 ]}มีการเขียนใหม่บางส่วนที่ลบข้อจำกัดขนาดคีย์/ค่า 4 GiB ออก อย่างไรก็ตาม การแก้ไขเหล่านั้นไม่เข้ากันกับรูปแบบดั้งเดิม เช่นVariable width CDB นี้ ซึ่งรองรับรูปแบบไฟล์ CDB ดั้งเดิม รวมถึงเวอร์ชัน 16 บิตและ 64 บิตด้วย

ในปี พ.ศ. 2552 cdb ทั้งหมดถูกนำไปไว้ในสาธารณสมบัติ^{[ 3 ]}

ที่สำคัญคือ ผู้สร้าง cdb ไม่ได้ตั้งใจให้ cdb ถูกใช้เป็นไลบรารีที่ใช้ร่วมกัน ซึ่งแตกต่างจากฐานข้อมูล ประเภทdbmอื่นๆ เกือบทั้งหมดเช่นBerkeley DB อย่างไรก็ตาม การเขียนโค้ดใหม่หลายๆ ตัวสามารถนำไปใช้เป็นไลบรารีที่ใช้ร่วมกันได้

• เว็บไซต์อย่างเป็นทางการของCDB
• คำอธิบายรูปแบบโดยละเอียดของโครงสร้างภายในของฐานข้อมูลค่าคงที่ (cdb)
• การนำไปใช้งานใหม่และการอธิบายมีคำอธิบายรูปแบบโดยละเอียดอยู่ในไฟล์ "readme.md"
• ผลการทดสอบประสิทธิภาพ QDBM ที่เก็บถาวรไว้เมื่อวันที่ 5 มีนาคม 2012 ในWayback Machineเปรียบเทียบ cdb กับโปรแกรมที่คล้ายคลึงกัน