แบบสอบถามฐานข้อมูลที่เหมาะสมที่สุดสำหรับการค้นหาคำนำหน้า

ฉันมีชุดข้อมูลซึ่งเป็นรายการช่วงคำนำหน้า และคำนำหน้ามีขนาดไม่เท่ากันทั้งหมด นี่คือตัวอย่างบางส่วน:

low: 54661601   high: 54661679   "bin": a
low: 526219100  high: 526219199  "bin": b
low: 4305870404 high: 4305870404 "bin": c

ฉันต้องการค้นหาว่า "bin" ใดที่สอดคล้องกับค่าเฉพาะพร้อมคำนำหน้าที่เกี่ยวข้อง ตัวอย่างเช่น ค่า 5466160179125211 จะสอดคล้องกับ "bin" a ในกรณีที่มีการทับซ้อนกัน (ซึ่งมีน้อย) เราสามารถส่งคืนคำนำหน้าที่ยาวที่สุดหรือคำนำหน้าทั้งหมดได้

เห็นได้ชัดว่าอัลกอริธึมที่เหมาะสมที่สุดคือต้นไม้ประเภทหนึ่งที่สามารถแทรกวัตถุถังขยะเข้าไปได้ โดยที่แต่ละระดับที่ต่อเนื่องกันของต้นไม้แสดงถึงคำนำหน้ามากขึ้นเรื่อยๆ

คำถามคือ เราจะนำสิ่งนี้ไปใช้ (ในแบบสอบถามเดียว) ในฐานข้อมูลได้อย่างไร อนุญาตให้แก้ไข/เพิ่มชุดข้อมูลได้ การออกแบบข้อมูลและการสืบค้นที่ดีที่สุดสำหรับสิ่งนี้คืออะไร คำตอบที่ใช้ mongo หรือ MySQL จะดีที่สุด


mysql mongodb prefix algorithm tree
person Peyton    schedule 15.06.2012    source แหล่งที่มา

คำตอบ (4)


arrow_upward
4
arrow_downward

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

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

{low: "54661601", high: "54661680", bin: "a"}
{low: "526219100",  high: "526219200",  bin: "b"}
{low: "4305870404", high: "4305870405", bin: "c"}

ตอนนี้ปัญหากลายเป็น: เมื่อพิจารณาจากชุดของช่วงเวลาหนึ่งมิติของรูปแบบ [ต่ำ, สูง) เราจะค้นหาได้อย่างรวดเร็วว่าช่วงใดมีจุดที่กำหนด ? วิธีที่ง่ายที่สุดในการทำเช่นนี้คือให้ดัชนีอยู่ในช่อง ต่ำ หรือ สูง ลองใช้ฟิลด์ สูง ในเปลือก Mongo:

db.coll.ensureIndex({high : 1})

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

db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(1).forEach(
       function(doc){ if (doc.low <= "5466160179125211") printjson(doc) } 
  )

สมมติว่าตอนนี้แทนที่จะสมมติว่าช่วงต่างๆ ไม่ทับซ้อนกันเลย คุณถือว่าทุกช่วงซ้อนทับกันโดยมีช่วงใกล้เคียงน้อยกว่า k (ฉันไม่รู้ว่าค่าของ k จะทำให้สิ่งนี้เป็นจริงสำหรับคุณ แต่หวังว่ามันจะเป็นเรื่องเล็ก) ในกรณีนั้น คุณสามารถแทนที่ 1 ด้วย k ใน "ขีดจำกัด" ด้านบนได้ เช่น

 db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(k).forEach(
       function(doc){ if (doc.low <= "5466160179125211") printjson(doc) } 
  )

อัลกอริทึมนี้ใช้เวลาทำงานเท่าใด ดัชนีจะถูกจัดเก็บโดยใช้ B-trees ดังนั้น หากมีช่วง n ในชุดข้อมูลของคุณ จะต้องใช้เวลา O(log n) ในการค้นหาเอกสารแรกที่ตรงกันโดย < ค่า strong>สูง จากนั้นจึงใช้เวลา O(k) เพื่อวนซ้ำเอกสาร k ถัดไป รวมเป็น O(log n em> + k) เวลา ถ้า k เป็นค่าคงที่ หรือจริงๆ แล้วมีค่าน้อยกว่า O(log n) นี่จะเป็นค่าที่เหมาะสมที่สุดเชิงกำกับเชิงกำกับ (นี่คือแบบจำลองมาตรฐานของการคำนวณ ฉันไม่ นับจำนวนการถ่ายโอนหน่วยความจำภายนอกหรืออะไรแฟนซี)

กรณีเดียวที่การแบ่งส่วนนี้คือเมื่อ k มีขนาดใหญ่ เช่น ถ้าช่วงขนาดใหญ่บางช่วงมีช่วงอื่นๆ เกือบทั้งหมด ในกรณีนี้ เวลาทำงานคือ O(n) หากข้อมูลของคุณมีโครงสร้างเช่นนี้ คุณอาจต้องการใช้วิธีการอื่น แนวทางหนึ่งคือการใช้การจัดทำดัชนี "2d" ของ mongo โดยมีค่า ต่ำ และ สูง ของคุณในการเข้ารหัสพิกัด x และ y . จากนั้นการสืบค้นของคุณจะสอดคล้องกับการสืบค้นจุดในภูมิภาคที่กำหนดของระนาบ x - y สิ่งนี้อาจทำได้ดีในทางปฏิบัติ แม้ว่าในปัจจุบันมีการใช้การจัดทำดัชนีแบบ 2 มิติ แต่กรณีที่แย่ที่สุดยังคงเป็น O(n)

มีผลลัพธ์ทางทฤษฎีจำนวนหนึ่งที่ได้รับประสิทธิภาพ O(log n) สำหรับค่าทั้งหมดของ k พวกมันใช้ชื่อต่างๆ เช่น ทรีการค้นหาลำดับความสำคัญ ทรีเซ็กเมนต์ ทรีช่วงเวลา ฯลฯ อย่างไรก็ตาม โครงสร้างข้อมูลเหล่านี้เป็นโครงสร้างข้อมูลสำหรับวัตถุประสงค์พิเศษที่คุณต้องนำไปใช้ด้วยตนเอง เท่าที่ฉันรู้ ขณะนี้ไม่มีฐานข้อมูลยอดนิยมใดที่นำไปใช้งาน

person matulef    schedule 16.06.2012

arrow_upward
0
arrow_downward

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

select bin from datatable where '5466160179125211' between low and high

หรือหากคุณมีเหตุผลบางประการที่จะเก็บค่าไว้เป็นจำนวนเต็มในตาราง คุณสามารถดำเนินการ CASTing ในแบบสอบถามได้

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

person Chud    schedule 15.06.2012

arrow_upward
0
arrow_downward

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

หากคุณต้องการทำอะไรที่ซับซ้อนกว่านี้ ฉันสงสัยว่าคุณต้องใช้แพลตฟอร์มอื่น

Sql Server มีประเภทข้อมูลลำดับชั้น: http://technet.microsoft.com/en-us/library/bb677173.aspx

PostgreSQL มีประเภทข้อมูล cidr ฉันไม่คุ้นเคยกับระดับการสนับสนุนการสืบค้นที่มี แต่ในทางทฤษฎีคุณสามารถสร้างตารางเส้นทางภายในฐานข้อมูลของคุณและใช้สิ่งนั้นเพื่อกำหนดที่เก็บข้อมูล: http://www.postgresql.org/docs/7.4/static/datatype-net-types.html#DATATYPE-CIDR

person Codure    schedule 15.06.2012

arrow_upward
0
arrow_downward

เพย์ตัน! :)

หากคุณต้องการเก็บทุกอย่างไว้เป็นจำนวนเต็ม และต้องการให้ทำงานกับแบบสอบถามเดียว สิ่งนี้ควรจะได้ผล:

select bin from datatable where 5466160179125211 between 
      low*pow(10, floor(log10(5466160179125211))-floor(log10(low))) 
   and ((high+1)*pow(10, floor(log10(5466160179125211))-floor(log10(high)))-1);

ในกรณีนี้ มันจะค้นหาระหว่างตัวเลข 5466160100000000 (ตัวเลขต่ำสุดที่มีคำนำหน้าต่ำและจำนวนหลักเดียวกันกับตัวเลขที่จะค้นหา) และ 546616799999999 (ตัวเลขสูงสุดที่มีคำนำหน้าสูงและจำนวนหลักเดียวกันกับตัวเลข การค้นหา). ซึ่งควรใช้ได้ในกรณีที่คำนำหน้าสูงมีตัวเลขมากกว่าคำนำหน้าต่ำ มันควรจะใช้งานได้ (ฉันคิดว่า) ในกรณีที่ตัวเลขสั้นกว่าความยาวของคำนำหน้า โดยที่โค้ด varchar ในโซลูชันก่อนหน้าสามารถให้ผลลัพธ์ที่ไม่ถูกต้องได้

คุณจะต้องทดลองเพื่อเปรียบเทียบประสิทธิภาพของการมีคณิตศาสตร์อินไลน์จำนวนมากในคิวรี (ดังเช่นในโซลูชันนี้) กับประสิทธิภาพของการใช้ varchars

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

select * from datatable2 where '5466' between low and high
    and length('5466') >= length(high);
person Jamie    schedule 15.06.2012