ในส่วนนี้ เราจะอธิบายวิธีที่ (2,4) -trees สามารถสนับสนุนการค้นหานิ้วอย่างมีประสิทธิภาพโดยการแนะนำการเชื่อมโยงระดับ แนวคิดที่อธิบายในส่วนนี้ยังนำไปใช้กับประเภททั่วไปของต้นไม้ที่มีความสูงสมดุลซึ่งแสดง (a, b) - ต้นไม้สำหรับ b ≥ 2a
ต้นไม้ (2,4)-ถูกกำหนดให้เป็นต้นไม้ค้นหาที่มีความสูงสมดุล โดยที่ใบทั้งหมดมีความลึกเท่ากัน และโหนดภายในทั้งหมดมีระดับสอง สามหรือสี่ องค์ประกอบจะถูกเก็บไว้ที่ใบไม้ และโหนดภายในเก็บเฉพาะคีย์การค้นหาเพื่อเป็นแนวทางในการค้นหา เนื่องจากแต่ละโหนดภายในมีดีกรีอย่างน้อยสอง จึงเป็นไปตามที่ (2,4) -tree มีความสูง O(log n) และรองรับการค้นหาในเวลา O(log n) คุณสมบัติที่สำคัญของ (2,4) -trees คือการแทรกและการลบโดยนิ้วใช้เวลาตัดจำหน่าย O(1) (คุณสมบัตินี้ไม่ได้ใช้ร่วมกันโดย (2, 3) -trees ซึ่งมีลำดับของการแทรก m และ การลบต้องใช้เวลา Θ(m log m)) นอกจากนี้ ต้นไม้ (2,4) ต้นที่มีใบ m สามารถแบ่งออกเป็นสองต้นขนาด m1 และ m2 ในเวลา O(log min(m1, m2)) ที่ตัดจำหน่าย ในทำนองเดียวกัน (2,4) - ต้นไม้ขนาด m1 และ m2 สามารถต่อกันได้ (ต่อกัน) ในเวลา O(log min(m1, m2)) ที่ตัดจำหน่าย
สำหรับการสนับสนุนการค้นหาด้วยนิ้ว (2,4) - ต้นไม้จะถูกเสริมด้วยลิงก์ระดับ เพื่อให้โหนดทั้งหมดที่มีความลึกเท่ากันจะถูกเชื่อมโยงเข้าด้วยกันในรายการที่เชื่อมโยงแบบคู่ รูปต่อไปนี้แสดง (2,4) -tree augmented พร้อมลิงก์ระดับ โปรดจำไว้ว่าขอบทั้งหมดแสดงถึงลิงก์แบบสองทิศทาง ลิงก์ระดับเพิ่มเติมนั้นตรงไปตรงมาเพื่อรักษาระหว่างการแทรก การลบ การแยก และการรวม (2,4) -trees
เพื่อทำการค้นหานิ้วจาก X ถึง Y ให้สำเร็จ ก่อนอื่นให้ตรวจสอบก่อนว่า Y อยู่ทางซ้ายหรือขวาของ X สมมติโดยไม่สูญเสียความทั่วไปว่า Y อยู่ทางขวาของ X จากนั้นเราไปที่เส้นทางจาก X ไปยังรูทขณะตรวจสอบ โหนด V บนเส้นทางและเพื่อนบ้านด้านขวาจนกว่าจะมีการระบุ Y อยู่ภายในทรีย่อยที่รูทที่ V หรือเพื่อนบ้านด้านขวาของ V การค้นหาด้านบนจะสิ้นสุดลงและการค้นหา y ล่างสุดสองครั้งเริ่มต้นที่เพื่อนบ้านขวาของ V และ/หรือ V ตามลำดับ ในรูปที่ 1 ตัวชี้ตามระหว่างการค้นหาด้วยนิ้วจาก j ถึง t จะแสดงด้วยเส้นหนา
เวลาค้นหา O(log d) เกิดขึ้นจากการสังเกตว่าถ้าเราเลื่อนการค้นหาขึ้นไปที่พาเรนต์ของโหนด V แล้ว Y จะอยู่ทางด้านขวาของทรีย่อยซ้ายสุดของเพื่อนบ้านทางขวาของ V นั่นคือ d เป็นอย่างน้อยในเลขชี้กำลัง ความสูงถึงตอนนี้
ในรูปที่ 1 เราเลื่อนจากโหนดภายในที่มีป้ายกำกับ “l n” ไปยังโหนดที่ระบุว่า “h” เพราะจาก “s” เรารู้ว่า Y อยู่ทางด้านขวาของทรีย่อยที่โหนด “q r”
การสร้างระดับที่เชื่อมโยง (2,4) -trees ทั่วไปโดยตรงกับระดับที่เชื่อมโยง (a, b) -trees ที่สามารถนำไปใช้ในหน่วยความจำภายนอก โดยการเลือก a =2b และ b เพื่อให้โหนดภายในพอดีกับบล็อกในหน่วยความจำภายนอก เราได้ต้นไม้การค้นหาหน่วยความจำภายนอกที่รองรับการแทรกและการลบในการถ่ายโอนหน่วยความจำ O(1) และการค้นหานิ้วด้วยการถ่ายโอนหน่วยความจำ O(logb n) .
