Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ในสาขาวิชาวิทยาการคอมพิวเตอร์ ต้นไม้แบบที (T-tree) เป็นโครงสร้างข้อมูลประเภท ต้นไม้ทวิภาค ที่ถูกใช้เป็น ฐานข้อมูลหน่วยความจำหลัก (main-memory database) เช่น Datablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen และ Kairos
ต้นไม้แบบที เป็นต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ (Self-balancing binary search tree) เหมาะสำหรับกรณีที่หน่วยความจำเก็บทั้งดัชนีและข้อมูลเช่นเดียวกับ ต้นไม้แบบบี (B-tree) ที่เหมาะสำหรับการรักษาข้อมูลของหน่วยความจำสำรอง เช่น ฮาร์ดดิสก์ นอกจากนี้ต้นไม้แบบทียังได้ประโยชน์จากโครงสร้างหน่วยความจำแบบต้นไม้เช่นเดียวกับ (AVL tree) ในขณะที่สามารถประหยัดพื้นที่เก็บข้อมูลเมื่อมีขนาดเป็นจำนวนมากได้ เพราะว่าแต่ละปมของต้นไม้เอวีแอลสามารถเก็บข้อมูลได้เพียงแค่ตัวเดียว จึงจำเป็นที่ต้องสร้างปมเพื่อเก็บข้อมูลเป็นจำนวนมากกว่า
ต้นไม้แบบทีจะใช้ความจริงที่ว่าข้อมูลจะอยู่ร่วมกันกับดัชนีในหน่วยความจำเสมอ มันจึงสามารถเก็บเฉพาะตัวชี้ไปยังข้อมูลเท่านั้น
ชื่อ ต้นไม้แบบที มาจากรูปร่างของปมที่มีลักษณะเหมือนตัวอักษรในภาษาอังกฤษตัว T
ประสิทธิภาพ
แม้ว่าต้นไม้แบบทีจะถูกนำมาใช้กันอย่างแพร่หลายสำหรับฐานข้อมูลหน่วยความจำหลัก แต่การวิจัยเมื่อเร็วๆ นี้แสดงให้เห็นว่าจริงๆ แล้วมันไม่ได้ทำงานได้ดีกว่า ต้นไม้แบบบี เลย เมื่อใช้กับฮาร์ดแวร์สมัยใหม่
เหตุผลหลักน่าจะเป็นเพราะว่าสมมติฐานแบบเดิมที่บอกว่าอัตราการเข้าถึงแคชและหน่วยความจำหลักเท่ากันใช้ไม่ได้อีกต่อไป เนื่องจากในปัจจุบันอัตราการเข้าถึงแคชจะเร็วกว่าหน่วยความจำหลักมาก
โครงสร้างปม
ต้นไม้แบบที ประกอบจะประกอบไปด้วย ตัวชี้ไปยังปมพ่อ ตัวชี้ไปยังปมลูกซ้ายและขวา แถวลำดับของตัวชี้ข้อมูล และข้อมูลการควบคุมพิเศษ
ปมที่มี (subtree) สองต้น เรียกว่า ปมภายใน (internal nodes) ปมที่ไม่มี เรียกว่า ปมใบ (leaf nodes) และปมที่มีเพียงแต่ต้นเดียว เรียกว่า ปมครึ่งใบ (half-leaf nodes) ปมจะถูกเรียกว่า ปมขอบเขต (bounding node) สำหรับค่าหนึ่ง ถ้าค่านั้นอยู่ระหว่างค่าน้อยสุดและมากสุดของปมนั้น
ค่าที่มากที่สุดในต้นไม้ย่อยซ้ายของแต่ละปมภายใน เรียกว่า ขอบเขตล่างมากสุด (greatest lower bound) ค่าที่น้อยที่สุดในต้นไม้ย่อยขวาของแต่ละปมภายใน เรียกว่า ขอบเขตบนน้อยสุด (least upper bound) ซึ่งค่าทั้งสองนี้จะอยู่ที่ปมใบหรือปมครึ่งใบเสมอ ปมใบและปมครึ่งใบสามารถมีจำนวนข้อมูลได้ตั้งแต่หนึ่งจนถึงขนาดของแถวลำดับข้อมูล แต่จำนวนข้อมูลขั้นต่ำและมากสุดของปมภายในจะถูกกำหนดไว้ล่วงหน้าแล้ว
การสร้างบริการ
การค้นหาสมาชิก
- เริ่มค้นที่ปมราก
- ถ้าปมนั้นเป็นปมขอบเขตสำหรับค่าที่ต้องการหา จึงค้นค่าในแถวลำดับของข้อมูลของปมนั้น ถ้าไม่พบแสดงว่าไม่มีค่านั้นอยู่
- ถ้าค่าที่ต้องการหามีค่าน้อยกว่าค่าน้อยสุดของปมนั้น ให้ค้นต่อที่ต้นไม้ย่อยซ้ายของมัน ถ้าไม่มีต้นไม้ย่อยซ้ายแสดงว่าไม่มีค่านั้นอยู่
- ถ้าค่าที่ต้องการหามีค่ามากกว่าค่ามากสุดของปมนั้น ให้ค้นต่อที่ต้นไม้ย่อยขวาของมัน ถ้าไม่มีต้นไม้ย่อยขวาแสดงว่าไม่มีค่านั้นอยู่
การเพิ่มสมาชิก
- ค้นหาปมขอบเขตของค่าที่ต้องการเพิ่ม ถ้ามีอยู่แล้ว
- ตรวจสอบว่ายังคงมีพื้นที่ว่างในแถวลำดับข้อมูลหรือไม่ ถ้ามีให้เพิ่มค่าใหม่และเสร็จสิ้น
- ถ้าไม่มีพื้นที่ว่างเหลือ ให้ลบตัวที่มีค่าน้อยสุดในปมนั้นและใส่ค่าใหม่ลงไป จากนั้นไปยังปมที่เก็บค่าขอบเขตล่างมากสุดไว้ เพื่อใส่ค่าน้อยสุดที่เคยลบไป ถ้าสามารถใส่ได้ให้ใส่เป็นค่ามากสุดของปมนี้ ถ้าใส่ไม่ได้ให้สร้างปมย่อยขวาใหม่แล้วใส่ค่าลงไป
- ถ้าไม่พบปมขอบเขตอยู่ ให้ใส่ค่าใหม่ในปมสุดท้ายที่ค้น ถ้าใส่ได้ค่าใหม่นี้จะกลายเป็นค่าน้อยสุดหรือไม่ก็มากสุดของปมนั้น ถ้าใส่ไม่ได้ให้สร้างต้นไม้ย่อยซ้ายหรือขวาใหม่
ถ้ามีการเพิ่มปมใหม่ ต้นไม้อาจจำเป็นต้องปรับสมดุล (rebalanced) จะอธิบายด้านล่าง
การลบสมาชิก
- ค้นหาปมขอบเขตของค่าที่ต้องการลบ ถ้าไม่พบแล้วเสร็จสิ้น
- ถ้าปมขอบเขตไม่ได้เก็บค่าที่ต้องการลบ แล้วเสร็จสิ้น
- ลบค่าจากแถวลำดับของปมนั้น หลังจากลบแล้วให้ดำเนินการตามประเภทของปม ดังนี้
- ปมภายใน: ถ้าจำนวนข้อมูลในแถวลำดับข้อมูลมีจำนวนน้อยกว่าขั้นต่ำที่จะใส่ได้ ให้ย้ายค่าขอบเขตล่างมากสุดของปมนี้มาใส่ หลังจากนั้นให้ดำเนินการตามหนึ่งในสองขั้นตอน สำหรับการลบออกจากปมใบ หรือปมครึ่งใบ
- ปมใบ: ถ้าปมนี้มีข้อมูลเพียงตัวเดียวในแถวลำดับข้อมูล ให้ลบปมนี้ทิ้ง จากนั้นปรับสมดุลหากจำเป็น
- ปมครึ่งใบ: ถ้าแถวลำดับของปมนี้สามารถผสานกับแถวลำดับของปมใบของปมนี้ได้โดยไม่เกินจำนวนมากสุดที่ใส่ได้ ให้ผสานกันและลบปมใบทิ้ง จากนั้นปรับสมดุลหากจำเป็น
การหมุนและการปรับสมดุล
ต้นไม้แบบทีจะดำเนินการบนพื้นฐานของ ต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ (Self-balancing binary search tree) โดยเฉพาะตามที่บทความของ Lehman และ Carey ได้อธิบายไว้ว่าต้นไม้แบบทีจะปรับสมดุลเหมือนกับต้นไม้เอวีแอล ที่ว่ามันจะไม่สมดุลเมื่อปมลูกมีความสูงต่างกันอย่างน้อยสองระดับ กรณีนี้จะเกิดขึ้นหลักจากทำการเพิ่มหรือลบปม ซึ่งหลังจากทำการเพิ่มหรือลบปมแล้ว ต้นไม้จะถูกตรวจจากใบไปยังราก ถ้าตรวจพบว่าไม่สมดุลก็จะทำการหมุนหนึ่งหรือสองครั้ง ทำให้สามารถประกันได้ว่าต้นไม้จะสมดุลเสมอ
เมื่อหมุนเสร็จแล้วปมภายในมีจำนวนข้อมูลน้อยกว่าขั้นต่ำที่ใส่ได้ให้ย้ายข้อมูลจากปมลูกมาใส่ในปมภายในนี้ (อาจมากกว่าหนึ่งปม)
ดูเพิ่ม
ต้นไม้แบบอื่น
อ้างอิง
- Tobin J. Lehman and Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986
- Rao, Jun; Kenneth A. Ross (1999). "Cache conscious indexing for decision-support in main memory" . Proceedings of the 25th International Conference on Very Large Databases (VLDB 1999). Morgan Kaufmann. pp. 78–89.
- Kim, Kyungwha; Junho Shim, and Ig-hoon Lee (2007). "Cache conscious trees: How do they perform on contemporary commodity microprocessors?". Proceedings of the 5th International Conference on Computational Science and Its Applications (ICCSA 2007). Springer. pp. 189–200.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisud insakhawichawithyakarkhxmphiwetxr tnimaebbthi T tree epnokhrngsrangkhxmulpraephth tnimthwiphakh thithukichepn thankhxmulhnwykhwamcahlk main memory database echn Datablitz eXtremeDB MySQL Cluster Oracle TimesTen aela Kairostwxyangtnimaebbthi tnimaebbthi epntnimkhnhaaebbthwiphakhthimiokhrngsrangprbsmdulexngid Self balancing binary search tree ehmaasahrbkrnithihnwykhwamcaekbthngdchniaelakhxmulechnediywkb tnimaebbbi B tree thiehmaasahrbkarrksakhxmulkhxnghnwykhwamcasarxng echn harddisk nxkcaknitnimaebbthiyngidpraoychncakokhrngsranghnwykhwamcaaebbtnimechnediywkb AVL tree inkhnathisamarthprahydphunthiekbkhxmulemuxmikhnadepncanwnmakid ephraawaaetlapmkhxngtnimexwiaexlsamarthekbkhxmulidephiyngaekhtwediyw cungcaepnthitxngsrangpmephuxekbkhxmulepncanwnmakkwa tnimaebbthicaichkhwamcringthiwakhxmulcaxyurwmknkbdchniinhnwykhwamcaesmx mncungsamarthekbechphaatwchiipyngkhxmulethann chux tnimaebbthi macakruprangkhxngpmthimilksnaehmuxntwxksrinphasaxngkvstw Tprasiththiphaphaemwatnimaebbthicathuknamaichknxyangaephrhlaysahrbthankhxmulhnwykhwamcahlk aetkarwicyemuxerw niaesdngihehnwacring aelwmnimidthanganiddikwa tnimaebbbi ely emuxichkbhardaewrsmyihm ehtuphlhlknacaepnephraawasmmtithanaebbedimthibxkwaxtrakarekhathungaekhchaelahnwykhwamcahlkethaknichimidxiktxip enuxngcakinpccubnxtrakarekhathungaekhchcaerwkwahnwykhwamcahlkmakokhrngsrangpmokhrngsrangpmkhxngtnimaebbthi tnimaebbthi prakxbcaprakxbipdwy twchiipyngpmphx twchiipyngpmluksayaelakhwa aethwladbkhxngtwchikhxmul aelakhxmulkarkhwbkhumphiess pmthimi subtree sxngtn eriykwa pmphayin internal nodes pmthiimmi eriykwa pmib leaf nodes aelapmthimiephiyngaettnediyw eriykwa pmkhrungib half leaf nodes pmcathukeriykwa pmkhxbekht bounding node sahrbkhahnung thakhannxyurahwangkhanxysudaelamaksudkhxngpmnn khakhxbekht khathimakthisudintnimyxysaykhxngaetlapmphayin eriykwa khxbekhtlangmaksud greatest lower bound khathinxythisudintnimyxykhwakhxngaetlapmphayin eriykwa khxbekhtbnnxysud least upper bound sungkhathngsxngnicaxyuthipmibhruxpmkhrungibesmx pmibaelapmkhrungibsamarthmicanwnkhxmulidtngaethnungcnthungkhnadkhxngaethwladbkhxmul aetcanwnkhxmulkhntaaelamaksudkhxngpmphayincathukkahndiwlwnghnaaelwkarsrangbrikarkarkhnhasmachik erimkhnthipmrak thapmnnepnpmkhxbekhtsahrbkhathitxngkarha cungkhnkhainaethwladbkhxngkhxmulkhxngpmnn thaimphbaesdngwaimmikhannxyu thakhathitxngkarhamikhanxykwakhanxysudkhxngpmnn ihkhntxthitnimyxysaykhxngmn thaimmitnimyxysayaesdngwaimmikhannxyu thakhathitxngkarhamikhamakkwakhamaksudkhxngpmnn ihkhntxthitnimyxykhwakhxngmn thaimmitnimyxykhwaaesdngwaimmikhannxyukarephimsmachik khnhapmkhxbekhtkhxngkhathitxngkarephim thamixyuaelw trwcsxbwayngkhngmiphunthiwanginaethwladbkhxmulhruxim thamiihephimkhaihmaelaesrcsin thaimmiphunthiwangehlux ihlbtwthimikhanxysudinpmnnaelaiskhaihmlngip caknnipyngpmthiekbkhakhxbekhtlangmaksudiw ephuxiskhanxysudthiekhylbip thasamarthisidihisepnkhamaksudkhxngpmni thaisimidihsrangpmyxykhwaihmaelwiskhalngip thaimphbpmkhxbekhtxyu ihiskhaihminpmsudthaythikhn thaisidkhaihmnicaklayepnkhanxysudhruximkmaksudkhxngpmnn thaisimidihsrangtnimyxysayhruxkhwaihm thamikarephimpmihm tnimxaccaepntxngprbsmdul rebalanced caxthibaydanlang karlbsmachik khnhapmkhxbekhtkhxngkhathitxngkarlb thaimphbaelwesrcsin thapmkhxbekhtimidekbkhathitxngkarlb aelwesrcsin lbkhacakaethwladbkhxngpmnn hlngcaklbaelwihdaeninkartampraephthkhxngpm dngni pmphayin thacanwnkhxmulinaethwladbkhxmulmicanwnnxykwakhntathicaisid ihyaykhakhxbekhtlangmaksudkhxngpmnimais hlngcaknnihdaeninkartamhnunginsxngkhntxn sahrbkarlbxxkcakpmib hruxpmkhrungib pmib thapmnimikhxmulephiyngtwediywinaethwladbkhxmul ihlbpmnithing caknnprbsmdulhakcaepn pmkhrungib thaaethwladbkhxngpmnisamarthphsankbaethwladbkhxngpmibkhxngpmniidodyimekincanwnmaksudthiisid ihphsanknaelalbpmibthing caknnprbsmdulhakcaepnkarhmunaelakarprbsmdul tnimaebbthicadaeninkarbnphunthankhxng tnimkhnhaaebbthwiphakhthimiokhrngsrangprbsmdulexngid Self balancing binary search tree odyechphaatamthibthkhwamkhxng Lehman aela Carey idxthibayiwwatnimaebbthicaprbsmdulehmuxnkbtnimexwiaexl thiwamncaimsmdulemuxpmlukmikhwamsungtangknxyangnxysxngradb krninicaekidkhunhlkcakthakarephimhruxlbpm sunghlngcakthakarephimhruxlbpmaelw tnimcathuktrwccakibipyngrak thatrwcphbwaimsmdulkcathakarhmunhnunghruxsxngkhrng thaihsamarthpraknidwatnimcasmdulesmx emuxhmunesrcaelwpmphayinmicanwnkhxmulnxykwakhntathiisidihyaykhxmulcakpmlukmaisinpmphayinni xacmakkwahnungpm duephimokhrngsrangkhxmul tnim okhrngsrangkhxmul tnimaebbxun thriph tnimaedngda tnimbanxangxingTobin J Lehman and Michael J Carey A Study of Index Structures for Main Memory Database Management Systems VLDB 1986 Rao Jun Kenneth A Ross 1999 Cache conscious indexing for decision support in main memory Proceedings of the 25th International Conference on Very Large Databases VLDB 1999 Morgan Kaufmann pp 78 89 Kim Kyungwha Junho Shim and Ig hoon Lee 2007 Cache conscious trees How do they perform on contemporary commodity microprocessors Proceedings of the 5th International Conference on Computational Science and Its Applications ICCSA 2007 Springer pp 189 200