เฮ้ ฮับ! ฉันขอเสนอการแปลบทความให้คุณทราบ
“ฐานข้อมูลเชิงสัมพันธ์ทำงานอย่างไร”.

เมื่อพูดถึงฐานข้อมูลเชิงสัมพันธ์ ฉันอดไม่ได้ที่จะคิดว่ามีบางอย่างขาดหายไป พวกเขาถูกใช้ทุกที่ มีฐานข้อมูลที่แตกต่างกันมากมาย ตั้งแต่ SQLite ขนาดเล็กที่มีประโยชน์ไปจนถึง Teradata อันทรงพลัง แต่มีเพียงไม่กี่บทความที่อธิบายวิธีการทำงานของฐานข้อมูล คุณสามารถค้นหาด้วยตัวเองโดยใช้ "ฐานข้อมูล Howdoesarelational" เพื่อดูว่ามีผลลัพธ์น้อยเพียงใด นอกจากนี้บทความเหล่านี้ยังสั้นอีกด้วย หากคุณกำลังมองหาเทคโนโลยี buzzy ล่าสุด (BigData, NoSQL หรือ JavaScript) คุณจะพบบทความเชิงลึกเพิ่มเติมที่อธิบายวิธีการทำงาน

ฐานข้อมูลเชิงสัมพันธ์เก่าเกินไปและน่าเบื่อเกินกว่าจะอธิบายนอกหลักสูตรของมหาวิทยาลัย เอกสารวิจัย และหนังสือหรือไม่?

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

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

ฉันจะเริ่มต้นด้วยพื้นฐานด้านวิทยาการคอมพิวเตอร์ เช่น ความซับซ้อนของเวลาของอัลกอริทึม (BigO) ฉันรู้ว่าพวกคุณบางคนเกลียดแนวคิดนี้ แต่ถ้าไม่มี คุณจะไม่สามารถเข้าใจความซับซ้อนภายในฐานข้อมูลได้ เนื่องจากนี่เป็นหัวข้อใหญ่ ฉันจะมุ่งเน้นไปที่ สิ่งที่ฉันคิดว่าสำคัญ: ฐานข้อมูลประมวลผลอย่างไร SQL สอบถามรายละเอียดเพิ่มเติม. ฉันแค่จะแนะนำ แนวคิดพื้นฐานของฐานข้อมูลเพื่อที่ตอนท้ายของบทความ คุณจะมีความคิดว่าเกิดอะไรขึ้นภายใต้ประทุน

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

เพื่อให้ท่านมีความรู้มากขึ้น บทความนี้จะแบ่งออกเป็น 3 ส่วน คือ

• ภาพรวมของส่วนประกอบฐานข้อมูลระดับต่ำและระดับสูง
• ภาพรวมของกระบวนการเพิ่มประสิทธิภาพแบบสอบถาม
• ภาพรวมของการจัดการธุรกรรมและบัฟเฟอร์พูล

กลับไปสู่พื้นฐาน

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

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

O(1) กับ O(n2)

ทุกวันนี้ Developer หลายๆ คนไม่สนใจเรื่องความซับซ้อนของเวลาของอัลกอริธึม... และพวกเขาก็พูดถูก!

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

แนวคิด

ความซับซ้อนของเวลาของอัลกอริทึม ใช้เพื่อดูว่าอัลกอริทึมจะใช้เวลานานเท่าใดจึงจะเสร็จสมบูรณ์ตามจำนวนข้อมูลที่กำหนด. เพื่ออธิบายความซับซ้อนนี้ เราใช้สัญกรณ์ทางคณิตศาสตร์ O ขนาดใหญ่ สัญกรณ์นี้ใช้กับฟังก์ชันที่อธิบายจำนวนการดำเนินการที่อัลกอริทึมต้องการสำหรับจำนวนอินพุตที่กำหนด

ตัวอย่างเช่น เมื่อฉันพูดว่า "อัลกอริทึมนี้มีความซับซ้อน O(some_function())" หมายความว่าอัลกอริทึมต้องการการดำเนินการ some_function(a_certain_amount_of_data) เพื่อประมวลผลข้อมูลจำนวนหนึ่ง

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

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

• O(1) หรือความซับซ้อนคงที่ยังคงที่ (ไม่เช่นนั้นจะไม่เรียกว่าความซับซ้อนคงที่)
• O(เข้าสู่ระบบ(n)) ยังคงต่ำแม้จะมีข้อมูลนับพันล้าน.
• ความยากที่เลวร้ายที่สุด - O(n2) โดยที่จำนวนการดำเนินการเพิ่มขึ้นอย่างรวดเร็ว.
• ภาวะแทรกซ้อนอีกสองอย่างเพิ่มขึ้นอย่างรวดเร็วเช่นกัน

ตัวอย่าง

ด้วยข้อมูลจำนวนเล็กน้อย ความแตกต่างระหว่าง O(1) และ O(n2) จึงมีน้อยมาก ตัวอย่างเช่น สมมติว่าคุณมีอัลกอริทึมที่ต้องประมวลผลองค์ประกอบ 2000 รายการ

• อัลกอริธึม O(1) จะทำให้คุณเสียค่าใช้จ่าย 1 การดำเนินการ
• อัลกอริธึม O(log(n)) จะทำให้คุณเสียค่าใช้จ่ายในการดำเนินการ 7 ครั้ง
• อัลกอริธึม O(n) จะทำให้คุณเสียค่าใช้จ่าย 2 การดำเนินการ
• อัลกอริธึม O(n*log(n)) จะทำให้คุณเสียค่าใช้จ่ายในการดำเนินการ 14 ครั้ง
• อัลกอริธึม O(n2) จะทำให้คุณเสียเงิน 4 การดำเนินงาน

ความแตกต่างระหว่าง O(1) และ O(n2) ดูเหมือนจะใหญ่มาก (การดำเนินการ 4 ล้านครั้ง) แต่คุณจะสูญเสียเวลาสูงสุด 2 มิลลิวินาที เพียงแค่ถึงเวลากระพริบตา แท้จริงแล้วโปรเซสเซอร์สมัยใหม่สามารถประมวลผลได้ การดำเนินงานหลายร้อยล้านครั้งต่อวินาที. นี่คือเหตุผลว่าทำไมประสิทธิภาพและการเพิ่มประสิทธิภาพจึงไม่เป็นปัญหาในโครงการไอทีหลายๆ โครงการ

อย่างที่ฉันบอกไป การรู้แนวคิดนี้ยังคงเป็นสิ่งสำคัญเมื่อทำงานกับข้อมูลจำนวนมหาศาล หากครั้งนี้อัลกอริธึมต้องประมวลผลองค์ประกอบ 1 รายการ (ซึ่งไม่มากสำหรับฐานข้อมูล):

• อัลกอริธึม O(1) จะทำให้คุณเสียค่าใช้จ่าย 1 การดำเนินการ
• อัลกอริธึม O(log(n)) จะทำให้คุณเสียค่าใช้จ่ายในการดำเนินการ 14 ครั้ง
• อัลกอริธึม O(n) จะทำให้คุณเสียค่าใช้จ่าย 1 การดำเนินการ
• อัลกอริธึม O(n*log(n)) จะทำให้คุณเสียค่าใช้จ่ายในการดำเนินการ 14 ครั้ง
• อัลกอริธึม O(n2) จะทำให้คุณเสียค่าใช้จ่าย 1 การดำเนินงาน

ฉันยังไม่ได้ทำคณิตศาสตร์ แต่ฉันจะบอกว่าด้วยอัลกอริธึม O(n2) คุณจะมีเวลาดื่มกาแฟ (แม้แต่สองแก้วด้วยซ้ำ!) หากคุณเพิ่มอีก 0 ลงในโวลุ่มข้อมูล คุณจะมีเวลางีบหลับ

เรามาเจาะลึกกันดีกว่า

ข้อมูลของคุณ:

• การค้นหาตารางแฮชที่ดีจะค้นหาองค์ประกอบใน O(1)
• การค้นหาต้นไม้ที่มีความสมดุลจะสร้างผลลัพธ์เป็น O(log(n))
• การค้นหาอาร์เรย์จะให้ผลลัพธ์เป็น O(n)
• อัลกอริธึมการเรียงลำดับที่ดีที่สุดมีความซับซ้อน O(n*log(n))
• อัลกอริธึมการเรียงลำดับที่ไม่ดีมีความซับซ้อน O(n2)

หมายเหตุ: ในส่วนต่อไปนี้ เราจะเห็นอัลกอริทึมและโครงสร้างข้อมูลเหล่านี้

ความซับซ้อนของเวลาของอัลกอริทึมมีหลายประเภท:

• สถานการณ์กรณีโดยเฉลี่ย
• สถานการณ์กรณีที่ดีที่สุด
• และสถานการณ์กรณีที่เลวร้ายที่สุด

ความซับซ้อนของเวลามักเป็นกรณีที่เลวร้ายที่สุด

ฉันแค่พูดถึงความซับซ้อนของเวลาของอัลกอริทึมเท่านั้น แต่ความซับซ้อนยังใช้กับ:

• การใช้หน่วยความจำของอัลกอริทึม
• อัลกอริธึมการใช้ดิสก์ I/O

แน่นอนว่ายังมีภาวะแทรกซ้อนที่เลวร้ายยิ่งกว่า n2 เช่น:

• n4: นี่มันแย่มาก! อัลกอริธึมที่กล่าวถึงบางส่วนมีความซับซ้อนเช่นนี้
• 3n: นี่แย่ยิ่งกว่านั้นอีก! อัลกอริธึมอย่างหนึ่งที่เราจะเห็นในตอนกลางของบทความนี้มีความซับซ้อนเช่นนี้ (และจริงๆ แล้วมันถูกใช้ในฐานข้อมูลจำนวนมาก)
• แฟกทอเรียล n: คุณจะไม่ได้รับผลลัพธ์เลยแม้ว่าจะมีข้อมูลเพียงเล็กน้อยก็ตาม
• nn: หากคุณเผชิญกับความซับซ้อนนี้ คุณควรถามตัวเองว่านี่คือสาขากิจกรรมของคุณจริงๆ หรือไม่...

หมายเหตุ: ฉันไม่ได้ให้คำจำกัดความที่แท้จริงของการกำหนด O ขนาดใหญ่แก่คุณเป็นเพียงแนวคิดเท่านั้น สามารถอ่านบทความนี้ได้ที่ วิกิพีเดีย สำหรับคำจำกัดความที่แท้จริง (เส้นกำกับ)

ผสานเรียงลำดับ

คุณจะทำอย่างไรเมื่อคุณต้องการจัดเรียงคอลเลกชัน? อะไร คุณเรียกใช้ฟังก์ชัน sort()... โอเค เป็นคำตอบที่ดี... แต่สำหรับฐานข้อมูล คุณต้องเข้าใจว่าฟังก์ชัน sort() นี้ทำงานอย่างไร

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

ผสาน

เช่นเดียวกับอัลกอริธึมที่มีประโยชน์อื่นๆ การเรียงลำดับแบบผสานอาศัยกลเม็ด: การรวมอาร์เรย์ที่เรียงลำดับ 2 ตัวที่มีขนาด N/2 เข้ากับอาร์เรย์ที่เรียงลำดับองค์ประกอบ N มีค่าใช้จ่ายเพียงการดำเนินการ N รายการเท่านั้น การดำเนินการนี้เรียกว่าการรวม

เรามาดูกันว่าสิ่งนี้หมายถึงอะไรด้วยตัวอย่างง่ายๆ:

รูปนี้แสดงให้เห็นว่าในการสร้างอาร์เรย์ 8 องค์ประกอบที่เรียงลำดับสุดท้าย คุณจะต้องวนซ้ำเพียงครั้งเดียวในอาร์เรย์ 2 องค์ประกอบ 4 ตัว เนื่องจากอาร์เรย์ 4 องค์ประกอบทั้งสองถูกจัดเรียงแล้ว:

• 1) คุณเปรียบเทียบองค์ประกอบปัจจุบันทั้งสองในสองอาร์เรย์ (ที่จุดเริ่มต้นปัจจุบัน = อันดับแรก)
• 2) จากนั้นนำอันที่เล็กที่สุดมาใส่ลงในอาร์เรย์ 8 องค์ประกอบ
• 3) และย้ายไปยังองค์ประกอบถัดไปในอาร์เรย์ที่คุณเอาองค์ประกอบที่เล็กที่สุด
• และทำซ้ำ 1,2,3 จนกระทั่งถึงองค์ประกอบสุดท้ายของอาร์เรย์ตัวใดตัวหนึ่ง
• จากนั้นคุณนำองค์ประกอบที่เหลือของอาร์เรย์อื่นมารวมไว้ในอาร์เรย์ 8 องค์ประกอบ

วิธีนี้ใช้ได้ผลเนื่องจากมีการจัดเรียงอาร์เรย์ทั้ง 4 องค์ประกอบ ดังนั้นคุณจึงไม่ต้อง "ย้อนกลับ" ในอาร์เรย์เหล่านั้น

ตอนนี้เราเข้าใจเคล็ดลับแล้ว นี่คือรหัสเทียมของฉันสำหรับการผสาน:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

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

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

ระยะการแบ่ง

ในขั้นตอนการหาร อาร์เรย์จะถูกแบ่งออกเป็นอาร์เรย์แบบรวม 3 ขั้นตอน จำนวนขั้นตอนที่เป็นทางการคือ log(N) (เนื่องจาก N=8, log(N) = 3)

ฉันจะรู้เรื่องนี้ได้อย่างไร

ฉันอัจฉริยะ! ในคำ - คณิตศาสตร์ แนวคิดก็คือแต่ละขั้นตอนจะแบ่งขนาดของอาร์เรย์ดั้งเดิมเป็น 2 จำนวนขั้นตอนคือจำนวนครั้งที่คุณสามารถแบ่งอาร์เรย์ดั้งเดิมออกเป็นสองส่วนได้ นี่คือคำจำกัดความที่แน่นอนของลอการิทึม (ฐาน 2)

ขั้นตอนการเรียงลำดับ

ในขั้นตอนการเรียงลำดับ คุณจะเริ่มต้นด้วยอาร์เรย์แบบรวม (องค์ประกอบเดียว) ในแต่ละขั้นตอน คุณจะใช้การดำเนินการผสานหลายรายการ และต้นทุนรวมคือ N = 8 การดำเนินการ:

• ในระยะแรก คุณจะมีการรวม 4 รายการซึ่งมีค่าใช้จ่าย 2 การดำเนินการในแต่ละครั้ง
• ในขั้นตอนที่สอง คุณจะมีการรวม 2 รายการซึ่งมีค่าใช้จ่าย 4 การดำเนินการในแต่ละครั้ง
• ในขั้นตอนที่สาม คุณจะมีการรวม 1 ครั้งซึ่งมีค่าใช้จ่าย 8 การดำเนินการ

เนื่องจากมีขั้นตอนบันทึก (N) ต้นทุนรวม N * การดำเนินการบันทึก (N).

ข้อดีของการเรียงลำดับแบบผสาน

เหตุใดอัลกอริทึมนี้จึงทรงพลังมาก

เพราะ:

• คุณสามารถเปลี่ยนเพื่อลดพื้นที่หน่วยความจำ เพื่อที่คุณจะได้ไม่ต้องสร้างอาร์เรย์ใหม่ แต่แก้ไขอาร์เรย์อินพุตโดยตรง

หมายเหตุ: อัลกอริทึมประเภทนี้เรียกว่า in-สถานที่ (เรียงลำดับโดยไม่มีหน่วยความจำเพิ่มเติม)

• คุณสามารถเปลี่ยนให้ใช้เนื้อที่ดิสก์และหน่วยความจำจำนวนเล็กน้อยพร้อมกันได้ โดยไม่ทำให้โอเวอร์เฮดของดิสก์ I/O มีนัยสำคัญ แนวคิดคือการโหลดเฉพาะส่วนที่กำลังประมวลผลลงในหน่วยความจำเท่านั้น นี่เป็นสิ่งสำคัญเมื่อคุณต้องการเรียงลำดับตารางหลายกิกะไบต์ที่มีบัฟเฟอร์หน่วยความจำเพียง 100 เมกะไบต์

หมายเหตุ: อัลกอริทึมประเภทนี้เรียกว่า การเรียงลำดับภายนอก.

• คุณสามารถเปลี่ยนให้ทำงานบนหลายกระบวนการ/เธรด/เซิร์ฟเวอร์ได้

ตัวอย่างเช่น การเรียงลำดับการผสานแบบกระจายเป็นหนึ่งในองค์ประกอบสำคัญ Hadoop (ซึ่งเป็นโครงสร้างในข้อมูลขนาดใหญ่)

• อัลกอริทึมนี้สามารถเปลี่ยนตะกั่วให้เป็นทองคำได้ (จริง ๆ!)

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

ตารางอาร์เรย์ ต้นไม้ และแฮช

ตอนนี้เราเข้าใจแนวคิดเรื่องความซับซ้อนและการเรียงลำดับของเวลาแล้ว ฉันควรจะบอกคุณเกี่ยวกับโครงสร้างข้อมูล 3 โครงสร้าง นี่เป็นสิ่งสำคัญเพราะพวกเขา เป็นพื้นฐานของฐานข้อมูลสมัยใหม่. ฉันจะแนะนำแนวคิดนี้ด้วย ดัชนีฐานข้อมูล.

Массив

อาร์เรย์สองมิติเป็นโครงสร้างข้อมูลที่ง่ายที่สุด ตารางสามารถถือเป็นอาร์เรย์ได้ ตัวอย่างเช่น:

อาร์เรย์ 2 มิตินี้เป็นตารางที่มีแถวและคอลัมน์:

• แต่ละบรรทัดแสดงถึงเอนทิตี
• คอลัมน์เก็บคุณสมบัติที่อธิบายเอนทิตี
• แต่ละคอลัมน์จัดเก็บข้อมูลประเภทเฉพาะ (จำนวนเต็ม สตริง วันที่...)

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

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

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

แผนผังฐานข้อมูลและดัชนี

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

• มากกว่าคีย์ทั้งหมดที่จัดเก็บไว้ในแผนผังย่อยด้านซ้าย
• น้อยกว่าคีย์ทั้งหมดที่จัดเก็บไว้ในแผนผังย่อยด้านขวา

เรามาดูกันว่าสิ่งนี้หมายถึงอะไรด้วยสายตา

ความคิด

ต้นไม้ต้นนี้มีองค์ประกอบ N = 15 ตัว สมมติว่าฉันกำลังมองหา 208:

• ฉันเริ่มต้นที่รูทซึ่งมีคีย์คือ 136 ตั้งแต่ 136<208 ฉันดูแผนผังย่อยที่ถูกต้องของโหนด 136
• 398>208 ดังนั้นฉันจึงดูทรีย่อยด้านซ้ายของโหนด 398
• 250>208 ดังนั้นฉันจึงดูทรีย่อยด้านซ้ายของโหนด 250
• 200<208 ดังนั้นฉันกำลังดูแผนผังย่อยที่ถูกต้องของโหนด 200 แต่ 200 ไม่มีแผนผังย่อยที่ถูกต้อง ไม่มีค่าอยู่ (เพราะถ้ามีอยู่ก็จะอยู่ในแผนผังย่อยด้านขวา 200)

ตอนนี้ สมมุติว่าฉันกำลังมองหา 40

• ฉันเริ่มต้นที่รูทซึ่งมีคีย์คือ 136 เนื่องจาก 136 > 40 ฉันดูที่แผนผังย่อยด้านซ้ายของโหนด 136
• 80 > 40 ดังนั้นฉันจึงดูแผนผังย่อยด้านซ้ายของโหนด 80
• 40= 40, มีโหนดอยู่. ฉันดึงข้อมูล ID แถวภายในโหนด (ไม่แสดงในรูปภาพ) และดูในตารางเพื่อหา ID แถวที่กำหนด
• การรู้ ID แถวช่วยให้ฉันรู้ได้อย่างแน่ชัดว่าข้อมูลอยู่ที่ไหนในตาราง ดังนั้นฉันจึงสามารถดึงข้อมูลได้ทันที

ท้ายที่สุดแล้ว การค้นหาทั้งสองครั้งจะทำให้ฉันต้องเสียค่าใช้จ่ายตามจำนวนระดับภายในแผนผัง หากคุณอ่านส่วนที่เกี่ยวกับการเรียงลำดับแบบผสานอย่างละเอียด คุณจะเห็นว่ามีระดับบันทึก(N) ปรากฎว่า บันทึกต้นทุนการค้นหา(N), ไม่เลว!

กลับมาที่ปัญหาของเรากันดีกว่า

แต่นี่เป็นนามธรรมมาก ดังนั้นเรากลับมาที่ปัญหาของเรากันดีกว่า แทนที่จะเป็นจำนวนเต็มธรรมดา ลองจินตนาการถึงสตริงที่แสดงถึงประเทศของบุคคลในตารางก่อนหน้า สมมติว่าคุณมีต้นไม้ที่มีฟิลด์ "ประเทศ" (คอลัมน์ 3) ของตาราง:

• หากคุณต้องการทราบว่าใครทำงานในสหราชอาณาจักร
• คุณดูที่ต้นไม้เพื่อรับโหนดที่แสดงถึงบริเตนใหญ่
• ภายใน "UKnode" คุณจะพบตำแหน่งของบันทึกคนงานในสหราชอาณาจักร

การค้นหานี้จะทำให้การดำเนินการบันทึก (N) มีค่าใช้จ่ายแทนการดำเนินการ N หากคุณใช้อาร์เรย์โดยตรง สิ่งที่คุณเพิ่งนำเสนอคือ ดัชนีฐานข้อมูล.

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

B+ดัชนีต้นไม้

แม้ว่าแผนผังนี้จะทำงานได้ดีในการรับค่าเฉพาะ แต่ก็มีปัญหาใหญ่เมื่อคุณต้องการ รับองค์ประกอบหลายรายการระหว่างสองค่า. ซึ่งจะมีค่าใช้จ่าย O(N) เนื่องจากคุณจะต้องดูแต่ละโหนดในแผนผังและตรวจสอบว่าอยู่ระหว่างสองค่านี้หรือไม่ (เช่น ด้วยการเคลื่อนที่แบบเรียงลำดับของแผนผัง) นอกจากนี้ การดำเนินการนี้ไม่เป็นมิตรกับดิสก์ I/O เนื่องจากคุณต้องอ่านแผนผังทั้งหมด เราจำเป็นต้องหาวิธีดำเนินการอย่างมีประสิทธิภาพ คำขอช่วง. เพื่อแก้ไขปัญหานี้ ฐานข้อมูลสมัยใหม่ใช้เวอร์ชันแก้ไขของแผนผังก่อนหน้าที่เรียกว่า B+Tree ในแผนผัง B+Tree:

• เฉพาะโหนดต่ำสุด (ใบ) เก็บข้อมูล (ตำแหน่งของแถวในตารางที่เกี่ยวข้อง)
• โหนดที่เหลืออยู่ที่นี่ สำหรับการกำหนดเส้นทาง ไปยังโหนดที่ถูกต้อง ระหว่างการค้นหา.

อย่างที่คุณเห็น มีโหนดมากกว่านี้ (สองครั้ง) แท้จริงแล้ว คุณมีโหนดเพิ่มเติม "โหนดการตัดสินใจ" ซึ่งจะช่วยคุณค้นหาโหนดที่ถูกต้อง (ซึ่งจัดเก็บตำแหน่งของแถวในตารางที่เกี่ยวข้อง) แต่ความซับซ้อนในการค้นหายังคงเป็น O(log(N)) (มีเพียงระดับเดียวเท่านั้น) ความแตกต่างที่ยิ่งใหญ่ก็คือ โหนดในระดับล่างเชื่อมต่อกับผู้สืบทอด.

ด้วย B+Tree นี้ หากคุณกำลังมองหาค่าระหว่าง 40 ถึง 100:

• คุณเพียงแค่ต้องมองหา 40 (หรือค่าที่ใกล้เคียงที่สุดหลังจาก 40 หากไม่มี 40) เหมือนที่คุณทำกับแผนผังก่อนหน้า
• จากนั้นรวบรวมทายาท 40 คนโดยใช้ลิงก์ทายาทโดยตรงจนกว่าจะถึง 100

สมมติว่าคุณพบผู้สืบทอด M และทรีมี N โหนด การค้นหาบันทึกต้นทุนโหนดเฉพาะ (N) เช่นเดียวกับแผนผังก่อนหน้า แต่เมื่อคุณได้รับโหนดนี้แล้ว คุณจะได้รับผู้สืบทอด M ในการดำเนินการ M โดยมีการอ้างอิงถึงผู้สืบทอดของพวกเขา การค้นหานี้มีค่าใช้จ่ายเฉพาะ M+log(N) การดำเนินการเปรียบเทียบกับการดำเนินการ N บนแผนผังก่อนหน้า ยิ่งไปกว่านั้น คุณไม่จำเป็นต้องอ่านแผนผังทั้งหมด (เฉพาะโหนด M+log(N)) ซึ่งหมายถึงการใช้งานดิสก์น้อยลง หาก M มีขนาดเล็ก (เช่น 200 แถว) และ N มีขนาดใหญ่ (1 แถว) จะมีความแตกต่างอย่างมาก

แต่มีปัญหาใหม่ที่นี่ (อีกครั้ง!) หากคุณเพิ่มหรือลบแถวในฐานข้อมูล (และในดัชนี B+Tree ที่เกี่ยวข้อง):

• คุณต้องรักษาลำดับระหว่างโหนดภายใน B+Tree ไม่เช่นนั้นคุณจะไม่สามารถค้นหาโหนดภายในแผนผังที่ไม่ได้เรียงลำดับได้
• คุณต้องรักษาจำนวนระดับขั้นต่ำที่เป็นไปได้ใน B+Tree มิฉะนั้นความซับซ้อนของเวลา O(log(N)) จะกลายเป็น O(N)

กล่าวอีกนัยหนึ่ง B+Tree จะต้องเรียงลำดับตัวเองและมีความสมดุล โชคดีที่สิ่งนี้เป็นไปได้ด้วยการดำเนินการลบและแทรกอย่างชาญฉลาด แต่สิ่งนี้มีค่าใช้จ่าย: การแทรกและการลบในแผนผัง B+ มีค่าใช้จ่าย O(log(N)) นั่นเป็นเหตุให้บางท่านเคยได้ยินเช่นนั้น การใช้ดัชนีมากเกินไปไม่ใช่ความคิดที่ดี. จริงหรือ, คุณกำลังชะลอการแทรก/อัปเดต/ลบแถวในตารางอย่างรวดเร็วเนื่องจากฐานข้อมูลจำเป็นต้องอัปเดตดัชนีของตารางโดยใช้การดำเนินการ O(log(N)) ที่มีราคาแพงสำหรับแต่ละดัชนี นอกจากนี้ การเพิ่มดัชนียังหมายถึงภาระงานที่เพิ่มขึ้นอีกด้วย ผู้จัดการธุรกรรม (จะอธิบายไว้ท้ายบทความ)

สำหรับรายละเอียดเพิ่มเติม คุณสามารถดูบทความ Wikipedia ได้ที่ B+ต้นไม้. หากคุณต้องการตัวอย่างการนำ B+Tree ไปใช้ในฐานข้อมูล ลองดู บทความนี้ и บทความนี้ จากนักพัฒนา MySQL ชั้นนำ ทั้งสองมุ่งเน้นไปที่วิธีที่ InnoDB (เอ็นจิ้น MySQL) จัดการดัชนี

หมายเหตุ: ผู้อ่านบอกฉันว่า เนื่องจากการเพิ่มประสิทธิภาพในระดับต่ำ แผนผัง B+ จึงควรมีความสมดุลอย่างสมบูรณ์

แฮชเทเบิล

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

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

• สำคัญ สำหรับองค์ประกอบของคุณ
• ฟังก์ชันแฮช สำหรับกุญแจ แฮชของคีย์ที่คำนวณแล้วจะให้ตำแหน่งขององค์ประกอบ (เรียกว่า เซ็กเมนต์ ).
• ฟังก์ชั่นสำหรับการเปรียบเทียบคีย์. เมื่อคุณพบกลุ่มที่ถูกต้องแล้ว คุณจะต้องค้นหาองค์ประกอบที่ต้องการภายในกลุ่มโดยใช้การเปรียบเทียบนี้

ตัวอย่างง่ายๆ

ลองยกตัวอย่างที่ชัดเจน:

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

• หากหลักสุดท้ายคือ 0 องค์ประกอบจะตกอยู่ในส่วน 0
• หากหลักสุดท้ายคือ 1 องค์ประกอบจะตกอยู่ในส่วน 1
• ถ้าหลักสุดท้ายคือ 2 องค์ประกอบนั้นจะตกอยู่ในพื้นที่ 2
• ...

ฟังก์ชันการเปรียบเทียบที่ฉันใช้คือความเท่าเทียมกันระหว่างจำนวนเต็มสองตัว

สมมติว่าคุณต้องการรับองค์ประกอบ 78:

• ตารางแฮชจะคำนวณรหัสแฮชสำหรับ 78 ซึ่งก็คือ 8
• ตารางแฮชดูที่ส่วนที่ 8 และองค์ประกอบแรกที่พบคือ 78
• เธอคืนสินค้า 78 ให้คุณ
• การค้นหามีค่าใช้จ่ายเพียง 2 การดำเนินการ (อันหนึ่งเพื่อคำนวณค่าแฮชและอีกอันเพื่อค้นหาองค์ประกอบภายในเซ็กเมนต์)

ตอนนี้ สมมติว่าคุณต้องการรับองค์ประกอบ 59:

• ตารางแฮชจะคำนวณรหัสแฮชสำหรับ 59 ซึ่งก็คือ 9
• ตารางแฮชค้นหาในส่วนที่ 9 องค์ประกอบแรกที่พบคือ 99 เนื่องจาก 99!=59 องค์ประกอบ 99 จึงไม่ใช่องค์ประกอบที่ถูกต้อง
• เมื่อใช้ตรรกะเดียวกัน องค์ประกอบที่สอง (9) องค์ประกอบที่สาม (79) ... องค์ประกอบสุดท้าย (29) จะถูกนำไปใช้
• ไม่พบองค์ประกอบ
• การค้นหามีค่าใช้จ่าย 7 การดำเนินการ.

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

อย่างที่คุณเห็น ราคาไม่เท่ากัน ขึ้นอยู่กับความคุ้มค่าที่คุณกำลังมองหา!

หากตอนนี้ฉันเปลี่ยนฟังก์ชันแฮชแบบโมดูโล 1 ของคีย์ (นั่นคือ ใช้ตัวเลข 000 หลักสุดท้าย) การค้นหาครั้งที่สองจะมีค่าใช้จ่ายเพียง 000 การดำเนินการเท่านั้น เนื่องจากไม่มีองค์ประกอบในส่วน 6 ความท้าทายที่แท้จริงคือการหาฟังก์ชันแฮชที่ดีซึ่งจะสร้างที่เก็บข้อมูลที่มีองค์ประกอบจำนวนน้อยมาก.

ในตัวอย่างของฉัน การค้นหาฟังก์ชันแฮชที่ดีนั้นเป็นเรื่องง่าย แต่นี่เป็นตัวอย่างง่ายๆ การค้นหาฟังก์ชันแฮชที่ดีนั้นยากกว่าเมื่อคีย์คือ:

• สตริง (เช่น - นามสกุล)
• 2 บรรทัด (เช่น - นามสกุลและชื่อ)
• 2 บรรทัดและวันที่ (เช่น - นามสกุล ชื่อจริง และวันเดือนปีเกิด)
• ...

ด้วยฟังก์ชันแฮชที่ดี การค้นหาตารางแฮชจะมีต้นทุน O(1).

ตารางอาร์เรย์และแฮช

ทำไมไม่ใช้อาร์เรย์?

อืม เป็นคำถามที่ดี

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

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

ที่มา: will.com