ബി-ട്രീ
കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിൽ, ബി-ട്രീ എന്നത് എപ്പോഴും ബാലൻസ് ആയി നിലനില്ക്കുകയും, ഡാറ്റയെ നിശ്ചിത ക്രമത്തിൽ പരിപാലിക്കുകയും, തിരയലുകൾ, തുടർച്ചയായ ആക്സസ്, ഉൾപ്പെടുത്തലുകൾ, ഇല്ലാതാക്കലുകൾ എന്നിവ ലോഗരിതിമിക് സമയത്തിൽ കൈകാര്യം ചെയ്യുന്നതിന് സഹായിക്കുകുയും ചെയ്യുന്ന ഒരു ട്രീ ഡാറ്റ സ്രക്ചറാണ്. ബൈനറി സെർച്ച് ട്രീയുടെ പൊതുവായ രൂപമാണ് ബി-ട്രീ. ബൈനറി സെർച്ച് ട്രീയിലെന്ന പോലെ ഒരു നോഡിന്റെ ഇടതുഭാഗത്തുള്ള സബ് ട്രീയിലെ എല്ലാ നോഡുകളിലെയും ഡാറ്റ പാരന്റ് നോഡിലെ ഡാറ്റയെക്കാൾ ചെറുതും, വലതുഭാഗത്തുള്ള സബ് ട്രീയിലെ എല്ലാ നോഡുകളിലെയും ഡാറ്റ പാരന്റ് നോഡിലെ ഡാറ്റയെക്കാൾ വലുതുമായിരിക്കും. ഓരോ നോഡിനും രണ്ടിൽകൂടുതൽ സബ്-ട്രീകളും അനുവദനീയമാണ്. ഡാറ്റാബേസുകൾ, ഫയൽ സിസ്റ്റങ്ങൾ എന്നിവ പോലുള്ള താരതമ്യേന വലിയ ഡാറ്റ ബ്ലോക്കുകൾ കൈകാര്യം ചെയ്യേണ്ടുന്ന സ്റ്റോറേജ് സംവിധാനങ്ങൾക്ക് ബി-ട്രീ അനുയോജ്യമാണ്.
| ബി-ട്രീ | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| തരം | ട്രീ (ഡാറ്റ സ്ട്രക്ചർ) | |||||||||||||||||||||||
| കണ്ടുപിടിച്ചത് | 1970[1] | |||||||||||||||||||||||
| കണ്ടുപിടിച്ചത് | റുഡോൾഫ് ബെയർ, എഡ്വേർഡ് എം. മക്ക്രൈറ്റ് | |||||||||||||||||||||||
| ||||||||||||||||||||||||
ചരിത്രം
തിരുത്തുകബോയിംഗ് റിസർച്ച് ലാബിൽ ജോലി ചെയ്യുന്നതിനിടെയാണ് റുഡോൾഫ് ബെയറും എഡ്വേർഡ് എം. മക്ക്രൈറ്റും വലിയ റാൻഡം ആക്സസ് ഫയലുകൾക്കായുള്ള ഇൻഡക്സ് കാര്യക്ഷമമായി കൈകാര്യം ചെയ്യുന്നതിനായി ബി-ട്രീകൾ കണ്ടുപിടിച്ചത്. ബി-ട്രീകളിലെ ബി എന്നത് ബോയിംഗ്, ബാലൻസ്ഡ്, ബിറ്റ്‍വീൻ, ബ്രോഡ്, ബുഷി, ബേയർ എന്നിവയിലേതിന്റെയെങ്കിലും ചുരുക്കരൂപമാണോ അല്ലയോ എന്ന് ബെയറും മക്രൈറ്റും ഒരിക്കലും വിശദീകരിച്ചിട്ടില്ല.[2][3][4]
നിർവചനം
തിരുത്തുകകമ്പ്യൂട്ടർ ശാസ്ത്രജ്ഞനായ (ക്)നുത്തിന്റെ നിർവചനമനുസരിച്ച്, താഴെപ്പറയുന്ന പ്രത്യേകതകളുള്ള ഒരു ട്രീയെ m ഓർഡർ ഉള്ള ബി-ട്രീ ആയി കണക്കാക്കാം: [5]
- ഓരോ നോഡിനും പരമാവധി m ചിൽഡ്രൻ മാത്രമേ ഉണ്ടാകൂ.
- റൂട്ടും ലീഫുകളും ഒഴികെയുള്ള ഓരോ നോഡിനും കുറഞ്ഞത് ⌈m/2⌉ ചിൽഡ്രൻസ് ഉണ്ടായിരിക്കും. റൂട്ട് നോഡിനും ലീഫ് നോ‍ഡുകൾക്കും പരമാവധി പരിധി മാത്രമേ ഉണ്ടായിരിക്കൂ. കുറഞ്ഞ പരിധി ബാധകമല്ല
- എല്ലാ ലീഫ് നോഡുകളും ഒരേ ലെവലിൽ ആയിരിക്കും.
- ലീഫ് അല്ലാത്തതും k ചിൽഡ്രൻ ഉള്ളതുമായ ഒരു നോഡിൽ k-1 കീകൾ (ഡാറ്റ ആണ് കീ എന്നത് കൊണ്ട് ഉദ്ദേശിക്കുന്നത്) ഉണ്ടാകും.
ഉദാഹരണത്തിന് ഓർഡർ 5 ആയ ഒരു ബി-ട്രീയിലെ ഏത് നോഡിനും (ലീഫ്, റൂട്ട് നോഡുകൾ ഒഴികെ) കുറഞ്ഞത് 3 ചൈൽഡ് ട്രീകളും, പരമാവധി 5 ചൈൽഡ് ട്രീകളും ഉണ്ടാകും. അതുപോലെ കുറഞ്ഞത് 2 കീയും, പരമാവധി 4 കീയും ഉണ്ടാകും.
- ↑ Bayer, R.; McCreight, E. (July 1970). "Organization and maintenance of large ordered indices" (PDF). Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '70. Boeing Scientific Research Laboratories. p. 107. doi:10.1145/1734663.1734671. S2CID 26930249.
- ↑ Comer 1979, പുറം. 123 footnote 1.
- ↑ Weiner, Peter G. (30 August 2013). "4- Edward M McCreight".
- ↑ "Stanford Center for Professional Development". scpd.stanford.edu. Archived from the original on 2014-06-04. Retrieved 2011-01-16.
- ↑ Knuth 1998, പുറം. 483.