Жалпыланған Іздеу Ағашы: GiST құрылымы мен мүмкіндіктері

Кіріспе

Компьютерлік есепте, GiST немесе Жалпыланған Іздеу Ағашы – бұл дерек құрылымы және API, оны әртүрлі дискіге негізделген іздеу ағаштарын құру үшін пайдалануға болады. GiST – B+ ағашының жалпылануы болып табылады, ол сақталатын деректердің түрі немесе қызмет көрсетілетін сұраныстар туралы ешқандай болжам жасамай, бір мезгілде және қалпына келтірілетін биіктік бойынша теңдестірілген іздеу ағашы инфрақұрылымын қамтамасыз етеді. GiST-ті белгілі индекстердің, соның ішінде B+ ағаштар, R ағаштар, hB ағаштар, RD ағаштар және басқалардың кең ауқымын оңай іске асыруға болады; сонымен қатар жаңа деректер типтері үшін мамандандырылған индекстерді оңай әзірлеуге мүмкіндік береді. Ол төртбұрышты ағаштар немесе префикс ағаштары (трилер) сияқты биіктігі теңдестірілмеген ағаштарды іске асыру үшін тікелей қолданыла алмайды, бірақ префикс ағаштары сияқты, ол сығылуды, соның ішінде жоғалтулы сығылуды қолдайды. GiST супертоптардың иерархиясына табиғи түрде реттелген кез келген дерек түрі үшін пайдаланылуы мүмкін. Бұл дерек түрін қолдау және ағаш құрылымын тұрғысынан ғана емес, сонымен қатар кеңейту авторына кез келген сұраныс шарттарын қолдауға мүмкіндік береді. GiST – деректер базасы жүйелерінде бағдарламалық жасақтаманың кеңейтілуінің мысалы: ол жаңа ағаш негізделген индекстерді қолдау үшін деректер базасы жүйесінің оңай дамуына мүмкіндік береді. Ол мұны өзінің негізгі жүйелік инфрақұрылымын, индекстердің кең ауқымындағы түрлі индекс дизайндарының қосымшаға тән аспектілерін қамтуға жеткілікті тар API-ден бөліп шығару арқылы іске асырады. GiST инфрақұрылымдық коды дискідегі индекс беттерінің орналасуын, индекстерді іздеу және индекстерден жою алгоритмдерін, сондай-ақ жоғары бір мезгілдестік үшін беттік деңгейде құлыптау және апат жағдайында қалпына келтіру үшін алдын ала жазу сияқты күрделі транзакциялық мәліметтерді басқарады. Бұл жаңа ағаш негізделген индекстердің авторларына жаңа индекс түрінің ерекше ерекшеліктерін іске асыруға назар аударуға мүмкіндік береді, мысалы, деректер жиынтығының іздеу үшін қалай сипатталуы керек. GiST бастапқыда Бульдік таңдау сұрақтарына жауап беру үшін жобаланған болса да, ол жақын көршілерді іздеуді және үлкен деректер жиынтықтарында статистикалық жуықтаудың әртүрлі түрлерін де қолдай алады.

In computing, GiST or Generalized Search Tree, is a data structure and API that can be used to build a variety of disk based search trees. GiST is a generalization of the B+ tree, providing a concurrent and recoverable height balanced search tree infrastructure without making any assumptions about the type of data being stored, or the queries being serviced. GiST can be used to easily implement a range of well known indexes, including B+ trees, R trees, hB trees, RD trees, and many others; it also allows for easy development of specialized indexes for new data types. It cannot be used directly to implement non height balanced trees such as quad trees or prefix trees (tries), though like prefix trees it does support compression, including lossy compression. GiST can be used for any data type that can be naturally ordered into a hierarchy of supersets. Not only is it extensible in terms of data type support and tree layout, it allows the extension writer to support any query predicates that they choose. GiST is an example of software extensibility in the context of database systems: it allows the easy evolution of a database system to support new tree based indexes. It achieves this by factoring out its core system infrastructure from a narrow API that is sufficient to capture the application specific aspects of a wide variety of index designs. The GiST infrastructure code manages the layout of the index pages on disk, the algorithms for searching indexes and deleting from indexes, and complex transactional details such as page level locking for high concurrency and write ahead logging for crash recovery. This allows authors of new tree based indexes to focus on implementing the novel features of the new index type — for example, the way in which subsets of the data should be described for search — without becoming experts in database system internals. Although originally designed for answering Boolean selection queries, GiST can also support nearest neighbor search, and various forms of statistical approximation over large data sets.

Қолданылу

Ең көп қолданылатын GiST іске асырылымы PostgreSQL реляциялық деректер базасында жүзеге асырылған; сондай-ақ Informix Universal Server-де және дербес кітапхана ретінде libgist-те де іске асырылған.