B-tree (original) (raw)
وينبغي عدم الخلط مع التسلسل الثنائي الشجري (بالإنجليزية: Binary tree) بي تري (بالإنجليزية: B-tree) في علوم الحاسب هي بيانات متسلسلة شجريا tree data structure , ومتوازنه ذاتيا Self-Balancing وهي تساعد على بقاء البيانات مفروزة sorted وتسمح بالبحث searches ووالوصول المتسلسل sequential access والإدراج insertions والمسح deletions في ما يسمى logarithmic time , بي تري هي تعميم للبحث الشجري الثنائي حيث ان الرابط الواحد Node يمكن ان يكون له أكثر من فرعين (Children),. وعلى عكس البيانات المتسلسلة شجريا ومتوازنة ذاتيا، بي - تري هي الحل الامثل للنظم التي تقراء وتكتب الكميات الكبيرة من البيانات، بي تري هي مثال جيد لبنية البيانات للذاكرة الخارجية وهي مستخدمة بكثرة في قواعد البيانات ونظم الملفات.
| Property | Value |
|---|---|
| dbo:abstract | وينبغي عدم الخلط مع التسلسل الثنائي الشجري (بالإنجليزية: Binary tree) بي تري (بالإنجليزية: B-tree) في علوم الحاسب هي بيانات متسلسلة شجريا tree data structure , ومتوازنه ذاتيا Self-Balancing وهي تساعد على بقاء البيانات مفروزة sorted وتسمح بالبحث searches ووالوصول المتسلسل sequential access والإدراج insertions والمسح deletions في ما يسمى logarithmic time , بي تري هي تعميم للبحث الشجري الثنائي حيث ان الرابط الواحد Node يمكن ان يكون له أكثر من فرعين (Children),. وعلى عكس البيانات المتسلسلة شجريا ومتوازنة ذاتيا، بي - تري هي الحل الامثل للنظم التي تقراء وتكتب الكميات الكبيرة من البيانات، بي تري هي مثال جيد لبنية البيانات للذاكرة الخارجية وهي مستخدمة بكثرة في قواعد البيانات ونظم الملفات. (ar) B-strom je druh stromu. Je specifický tím, že má řád a limity na maximální, i minimální počet potomků vrcholu. B-strom je díky této vlastnosti vyvážený, operace přidání, vyjmutí i vyhledávání tedy probíhají v logaritmickém čase. Tato struktura je často používána v aplikacích, kdy není celá struktura uložena v operační paměti (RAM), ale v nějaké sekundární paměti, jako je pevný disk (například databáze). Protože přístup do tohoto typu paměti je náročný na čas (hlavně vyhledání náhodné položky), snažíme se minimalizovat počet přístupů do této paměti. Příklad: Máme-li B-strom hloubky 2 a počet potomků každého uzlu je 1 001, můžeme do něj uložit miliardu klíčů (obsahuje milion uzlů) a ke každé položce se dostaneme maximálně po dvou diskových operacích. B-strom je speciální případ (a,b)-stromu, který poskytuje větší volnost ve volbě minimálního a maximálního počtu potomků než B-strom. Autoři algoritmu, Rudolf Bayer a , nikdy nevysvětlili, co v názvu znamená písmeno B. Nejčastěji se předpokládá, že znamená balanced (v angličtině vyvážený), jelikož všechny listy jsou na stejné úrovni stromu. B může být také první písmeno jména Bayer, případně Boeing, oba totiž v té době pracovali ve výzkumném ústavu této firmy. (cs) En les ciències de la computació, els arbres-B o B-arbres són que es troben comunament en les implementacions de bases de dades i sistemes d'arxius. Els arbres B mantenen les dades ordenades i les insercions i eliminacions es realitzen en temps logarítmic amortitzat. (ca) In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children. Unlike other self-balancing binary search trees, the B-tree is well suited for storage systems that read and write relatively large blocks of data, such as databases and file systems. (en) En las ciencias de la computación, los árboles-B o B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Al igual que los árboles binarios de búsqueda, son árboles balanceados de búsqueda, pero cada nodo puede poseer más de dos hijos. Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado. (es) Ein B-Baum (englisch B-tree) ist in der Informatik eine Daten- oder Indexstruktur, die häufig in Datenbanken und Dateisystemen eingesetzt wird. Ein B-Baum ist ein immer vollständig balancierter Baum, der Daten nach Schlüsseln sortiert speichert. Er kann binär sein, ist aber im Allgemeinen kein Binärbaum. Das Einfügen, Suchen und Löschen von Daten in B-Bäumen ist in amortisiert logarithmischer Zeit möglich. B-Bäume wachsen und schrumpfen, anders als viele Suchbäume, von den Blättern hin zur Wurzel. (de) En informatique, un arbre B (appelé aussi B-arbre par analogie au terme anglais « B-tree ») est une structure de données en arbre équilibré. Les arbres B sont principalement mis en œuvre dans les mécanismes de gestion de bases de données et de systèmes de fichiers. Ils stockent les données sous une forme triée et permettent une exécution des opérations d'insertion et de suppression en temps toujours logarithmique. Le principe est de permettre aux nœuds parents de posséder plus de deux nœuds enfants : c'est une généralisation de l’arbre binaire de recherche. Ce principe minimise la taille de l'arbre et réduit le nombre d'opérations d'équilibrage. De plus un arbre B grandit à partir de la racine, contrairement à un arbre binaire de recherche qui croît à partir des feuilles. Le créateur des arbres B, Rudolf Bayer, n'a pas explicité la signification du « B ». L'explication la plus fréquente est que le B correspond au terme anglais « balanced » (en français : « équilibré »). Cependant, il pourrait aussi découler de « Bayer », du nom du créateur, ou de « Boeing », du nom de la firme pour laquelle le créateur travaillait (Boeing Scientific Research Labs). (fr) 전산학에서 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효율적이다. B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있다. 대부분의 이진 트리는 항목이 삽입될 때 하향식으로 구성되는 데 반해, B-트리는 일반적으로 상향식으로 구성된다. n개의 키 (s1,s2,s3...,sn)가 있는 한 노드를 생각해 보자. 키집합은 정렬되어 있다고 한다. (즉, s1 B-트리의 기본 개념은 내부 노드의 자식 노드의 수가 미리 정해진 범위 내에서 변경가능하다는 것이다. 항목이 삽입되거나 삭제될 때, 내부 노드는 해당 범위의 자식 노드의 수를 만족시키기 위해 분리되거나 혹은 다른 노드와 합쳐지게 된다. 자식 노드의 수가 일정 범위 내에서만 유지되면 되므로 분리 및 합침을 통한 재균형 과정은 다른 자가 균형 이진 탐색 트리만큼 자주 일어나지 않지만, 저장 공간에서의 손실은 있게 된다. 자식 노드의 최소 및 최대수는 일반적으로 특별한 구현에 대해서 결정되어 있다. 예를 들어, 2-3 B-트리(혹은 단순히 2-3 트리)에서 각 내부 노드는 2 또는 3개의 자식 노드를 가질 수 있다. 만약 허용되지 않은 수의 자식 노드를 가질 경우, 해당 내부 노드는 부적절한 상태에 있다고 한다. B-트리는 노드 접근시간이 노드에서의 연산시간에 비해 훨씬 길 경우, 다른 구현 방식에 비해 상당한 이점을 가지고 있다. 이는 대부분의 노드가 하드디스크와 같은 에 있을 때 일반적으로 일어난다. 각 내부 노드에 있는 자식 노드의 수를 최대화함으로써, 트리의 높이는 감소하며, 균형맞춤은 덜 일어나고, 효율은 증가하게 된다. 대개 이 값은 각 노드가 완전한 하나의 디스크 블록 혹은 2차 저장장치에서의 유사한 크기를 차지하도록 정해진다. B-트리의 창시자인 루돌프 바이어는 'B'가 무엇을 의미하는지 따로 언급하지는 않았다. 가장 가능성 있는 대답은 리프 노드를 같은 높이에서 유지시켜주므로 균형잡혀있다(balanced)는 뜻에서의 'B'라는 것이다. '바이어(Bayer)'의 'B'를 나타낸다는 의견도, 혹은 그가 일했던 보잉 과학 연구소(Boeing Scientific Research Labs)에서의 'B'를 나타낸다는 의견도 있다. (ko) B木（びーき、英:B-tree）は、計算機科学におけるデータ構造、特に木構造の一つ。ブロック単位のランダムアクセスが可能な補助記憶装置（ハードディスクドライブなど）上に木構造を実装するのに適した構造として知られる。 実システムでも多用されており、データベース管理システムの多くはB木による索引を実装している（B木の改良型または亜種であるB+木やB*木を使うことが多い）。 (ja) Un B-albero (in inglese: B-tree) è una struttura dati che permette la rapida localizzazione dei file (record o chiavi), specie nelle basi di dati, riducendo il numero di volte che un utente necessita per accedere alla memoria in cui il dato è salvato. Essi derivano dagli alberi binari di ricerca, in quanto ogni chiave appartenente al sottoalbero sinistro di un nodo è di valore inferiore rispetto a ogni chiave appartenente ai sottoalberi alla sua destra; inoltre, la loro struttura ne garantisce il : per ogni nodo, le altezze dei sottoalberi destro e sinistro differiscono al più di una unità. Questo è il vantaggio principale del B-albero, e permette di compiere operazioni di inserimento, cancellazione e ricerca in tempi ammortizzati logaritmicamente. Sono utilizzati spesso nell'ambito delle basi di dati, in quanto permettono di accedere ai nodi in maniera efficiente sia nel caso essi siano disponibili in memoria centrale (tramite una cache), sia qualora essi siano presenti solo sulla memoria di massa. (it) Em ciência da computação, uma árvore B é uma estrutura de dados em árvore, auto-balanceada, que armazena dados classificados e permite pesquisas, acesso sequencial, inserções e remoções em tempo logarítmico. A árvore B é uma generalização de uma árvore de pesquisa binária em que um nó pode ter mais que dois filhos. Diferente das árvores de pesquisa binária auto-balanceadas, a árvore B é bem adaptada para sistemas de armazenamento que leem e escrevem blocos de dados relativamente grandes, como discos. É normalmente usada em bancos de dados e sistemas de arquivos e foi projetada para funcionar especialmente em memória secundária como um disco magnético ou outros dispositivos de armazenamento secundário. As árvores B são semelhantes as árvores preto e vermelho, mas são melhores para minimizar operações de E/S de disco. Muitos sistemas de bancos de dados usam árvores B ou variações da mesma para armazenar informações. Dentre suas propriedades ela permite a inserção, remoção e busca de chaves numa complexidade temporal logarítmica e, por esse motivo, é muito empregada em aplicações que necessitam manipular grandes quantidades de informação tais como um banco de dados ou um sistemas de arquivos. Inventada por Rudolf Bayer e Edward Meyers McCreight em 1971 enquanto trabalhavam no Boeing Scientific Research Labs, a origem do nome (árvore B) não foi definida por estes. Especula-se que o B venha da palavra balanceamento, do nome de um de seus inventores Bayer ou de Boeing, nome da empresa. Árvores B são uma generalização das árvores binária de busca, pois cada nó de uma árvore binária armazena uma única chave de busca, enquanto as árvores B armazenam um número maior do que um de chaves de busca em cada nó, ou no termo mais usual para essa árvore, em cada página. Como a ideia principal das árvores B é trabalhar com dispositivos de memória secundária, quanto menos acessos a disco a estrutura de dados proporcionar, melhor será o desempenho do sistema na operação de busca sobre os dados manipulados. O que significa o B, se significa algo, nunca foi estabelecido. (pt) B-drzewo – drzewiasta struktura danych, przechowująca klucze w pewnym porządku i powiązane z nimi dane, używana przede wszystkim w systemach baz danych. Głównym pomysłem zastosowanym w B-drzewach jest struktura wewnętrznego węzła. Każdy węzeł może posiadać od do węzłów potomnych, gdzie to rząd B-drzewa; wyjątkiem jest korzeń, który może posiadać od do węzłów potomnych. Te założenia gwarantują, że wysokość drzewa zawierającego kluczy będzie niska, rzędu co też powoduje, że asymptotyczna złożoność czasowa operacji podstawowych: wyszukiwania, wstawiania i kasowania kluczy jest rzędu Niska wysokość drzewa powoduje, że liczba węzłów, które trzeba odczytać bądź zapisać, jest niewielka. W praktycznych zastosowaniach, w których informacje przechowywane są na dyskach twardych bądź płytach CD/DVD ma to fundamentalne znaczenie, bowiem czasy dostępu do tych urządzeń są dużo większe niż do pamięci wewnętrznej komputera i dominują w całkowitym czasie wykonywania operacji na danych (czasy dostępu do pamięci komputera rzędu mikro- lub setek nanosekund, natomiast do współczesnych dysków twardych to kilka milisekund – czyli 3–4 rzędy wielkości więcej). Z kolei zlokalizowanie odpowiedniego klucza bądź potomka w węźle wczytanym do pamięci wewnętrznej jest dużo szybsze, nawet jeśli rząd drzewa jest duży. (pl) Ett B-träd är en datastruktur i form av ett balanserat . Varje nod har mellan m och m/2 barn, där m är ett givet heltal större än 1. Roten kan ha så få som 2 stycken n. Den här strukturen kan vara användbar om stora delar av trädet finns i långsammare minnen (som en hårddisk) eftersom trädets höjd kan reduceras genom att man väljer ett stort m. (sv) B-дерево (по-русски произносится как Би-дерево) — структура данных, дерево поиска. С точки зрения внешнего логического представления — сбалансированное, сильно ветвистое дерево. Часто используется для хранения данных во внешней памяти. Использование B-деревьев впервые было предложено Р. Бэйером (англ. R. Bayer) и Э. МакКрейтом (англ. E. McCreight) в 1970 году. Сбалансированность означает, что длины любых двух путей от корня до листьев различаются не более, чем на единицу. Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков. С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц памяти, то есть каждому узлу дерева соответствует блок памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру. (ru) B树（英語：B-tree），是一种在计算机科学自平衡的树，能够保持数据有序。這種資料結構能夠讓查找數據、顺序访问、插入數據及刪除的動作，都在對數時間內完成。B树，概括来说是一个一般化的二元搜尋樹（binary search tree）一個節點可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。這種資料結構常被應用在数据库和文件系统的实现上。 (zh) Б-дерева (англ. B-tree) — це один з видів збалансованих дерев, що забезпечують ефективне збереження інформації на магнітних дисках та інших пристроях з прямим доступом. Б-дерева схожі на червоно-чорні, різниця в тому, що в Б-дереві вузол може мати багато дітей, на практиці до тисячі, залежно від характеристик використовуваного диска. Завдяки цьому константа в оцінці O(log n) для висоти дерева менша, ніж для червоно-чорних дерев. Як і червоно-чорні дерева, Б-дерева дозволяють реалізувати багато операцій з множинами розміру n за час O(log n). Вузол x, який зберігає n[x] ключів, має n[x]+1 дітей. Ключі, що зберігаються в x служать границями, що розділяють всіх його нащадків на n[x]+1 груп; за кожну групу відповідає один з нащадків x. При пошуку в Б-дереві ми порівнюємо шуканий ключ з n[x] ключами, що зберігаються в x, і за результатами порівняння вибираємо одного з n[x]+1 нащадків. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/B-tree.svg?width=300 |
| dbo:wikiPageExternalLink | http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html http://supertech.csail.mit.edu/cacheObliviousBTree.html http://www.bluerwhite.org/btree https://infolab.usc.edu/csci585/Spring2010/den_ar/indexing.pdf https://www.cs.usfca.edu/~galles/visualization/BTree.html https://ysangkok.github.io/js-clrs-btree/btree.html https://docs.microsoft.com/en-us/sql/t-sql/statements/bulk-insert-transact-sql%3Fview=sql-server-2017%7C http://opendatastructures.org/versions/edition-0.1g/ods-python/14_2_B_Trees.html http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html http://sop.codeplex.com https://archive.org/details/filestructures00folk https://ghostarchive.org/archive/20221009/http:/web.cs.ucdavis.edu/~green/courses/ecs165b-s10/Lecture6.pdf https://ghostarchive.org/archive/20221009/http:/www.cs.bilkent.edu.tr/~canf/CS281Spring15LectureNotesFeb13/Week13.pdf https://web.archive.org/web/20110708080729/http:/boilerbay.com/infinitydb/TheDesignOfTheInfinityDatabaseEngine.htm https://www.youtube.com/watch%3Fv=I22wEC1tTGo http://www.scholarpedia.org/article/B-tree_and_UB-tree http://web.cs.ucdavis.edu/~green/courses/ecs165b-s10/Lecture6.pdf http://www.cs.bilkent.edu.tr/~canf/CS281Spring15LectureNotesFeb13/Week13.pdf https://lib.dr.iastate.edu/cgi/viewcontent.cgi%3Farticle=2336&context=etd https://xlinux.nist.gov/dads/HTML/bstartree.html https://xlinux.nist.gov/dads/HTML/btree.html |
| dbo:wikiPageID | 4674 (xsd:integer) |
| dbo:wikiPageLength | 48522 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123980396 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Rudolf_Bayer dbr:Pat_Morin dbr:Index_(database) dbr:Bilkent_University dbr:Binary_search_tree dbr:Boeing dbr:Reiser4 dbr:Cylinder-head-sector dbr:University_of_California,_Davis dbr:Introduction_to_Algorithms dbr:T-tree dbr:Node_(computer_science) dbr:Order_statistic_tree dbr:R-tree dbr:Edward_M._McCreight dbr:Branching_factor dbr:NTFS dbr:Tree_data_structure dbr:Linux dbr:MS-DOS dbr:Subtree dbr:Computer_science dbr:B+_tree dbc:Computer-related_introductions_in_1971 dbr:Btrfs dbr:Acta_Informatica dbr:Tree_(data_structure) dbr:Lazy_deletion dbr:Leaf_node dbr:Linked_list dbr:2–3–4_tree dbr:APFS dbr:2–3_tree dbc:B-tree dbr:Database dbr:DragonFly_BSD dbr:Ext4 dbr:FAT12 dbr:File_Allocation_Table dbr:Page_cache dbr:Relational_database dbr:HAMMER_(file_system) dbr:Hierarchical_File_System dbr:Big_O_notation dbr:Block_(data_storage) dbr:TENEX_(operating_system) dbr:TOPS-20 dbr:Red–black_tree dbr:Donald_Knuth dbc:Database_index_techniques dbr:File_system dbr:HFS+ dbr:Internal_node dbr:Seek_time dbr:Outdegree dbr:ISAM dbr:The_Art_of_Computer_Programming dbr:Self-balancing_binary_search_tree dbr:Skip_list dbr:Secondary_storage dbr:Hard_drive dbr:Main_memory_database dbr:Binary_search dbr:Logarithmic_time dbr:File:B-tree.svg dbr:File:B_tree_insertion_example.png |
| dbp:date | February 2012 (en) |
| dbp:deleteAvg | O (en) |
| dbp:deleteWorst | O (en) |
| dbp:insertAvg | O (en) |
| dbp:insertWorst | O (en) |
| dbp:inventedBy | dbr:Rudolf_Bayer dbr:Edward_M._McCreight |
| dbp:inventedYear | 1970 (xsd:integer) |
| dbp:name | B-tree (en) |
| dbp:reason | the discussion below uses "element", "value", "key", "separator", and "separation value" to mean essentially the same thing. The terms are not clearly defined. There are some subtle issues at the root and leaves (en) |
| dbp:searchAvg | O (en) |
| dbp:searchWorst | O (en) |
| dbp:spaceAvg | O (en) |
| dbp:spaceWorst | O (en) |
| dbp:type | dbr:Tree_(data_structure) |
| dbp:wikiPageUsesTemplate | dbt:CS-Trees dbt:Citation dbt:Citation_needed dbt:Cite_thesis dbt:Cite_web dbt:Commons_category dbt:Confusing dbt:Distinguish dbt:Harv dbt:Math dbt:Mvar dbt:R dbt:Reflist dbt:Section_link dbt:Sfn dbt:Short_description dbt:Unreferenced_section dbt:Which dbt:Tone dbt:Floor dbt:Data_structures dbt:Infobox_data_structure |
| dcterms:subject | dbc:Computer-related_introductions_in_1971 dbc:B-tree dbc:Database_index_techniques |
| gold:hypernym | dbr:Structure |
| rdf:type | owl:Thing yago:Ability105616246 yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:Know-how105616786 yago:Method105660268 yago:PsychologicalFeature100023100 dbo:Building yago:Structure105726345 yago:Technique105665146 yago:WikicatDataStructures yago:WikicatDatabaseIndexTechniques |
| rdfs:comment | وينبغي عدم الخلط مع التسلسل الثنائي الشجري (بالإنجليزية: Binary tree) بي تري (بالإنجليزية: B-tree) في علوم الحاسب هي بيانات متسلسلة شجريا tree data structure , ومتوازنه ذاتيا Self-Balancing وهي تساعد على بقاء البيانات مفروزة sorted وتسمح بالبحث searches ووالوصول المتسلسل sequential access والإدراج insertions والمسح deletions في ما يسمى logarithmic time , بي تري هي تعميم للبحث الشجري الثنائي حيث ان الرابط الواحد Node يمكن ان يكون له أكثر من فرعين (Children),. وعلى عكس البيانات المتسلسلة شجريا ومتوازنة ذاتيا، بي - تري هي الحل الامثل للنظم التي تقراء وتكتب الكميات الكبيرة من البيانات، بي تري هي مثال جيد لبنية البيانات للذاكرة الخارجية وهي مستخدمة بكثرة في قواعد البيانات ونظم الملفات. (ar) En les ciències de la computació, els arbres-B o B-arbres són que es troben comunament en les implementacions de bases de dades i sistemes d'arxius. Els arbres B mantenen les dades ordenades i les insercions i eliminacions es realitzen en temps logarítmic amortitzat. (ca) In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children. Unlike other self-balancing binary search trees, the B-tree is well suited for storage systems that read and write relatively large blocks of data, such as databases and file systems. (en) En las ciencias de la computación, los árboles-B o B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Al igual que los árboles binarios de búsqueda, son árboles balanceados de búsqueda, pero cada nodo puede poseer más de dos hijos. Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado. (es) Ein B-Baum (englisch B-tree) ist in der Informatik eine Daten- oder Indexstruktur, die häufig in Datenbanken und Dateisystemen eingesetzt wird. Ein B-Baum ist ein immer vollständig balancierter Baum, der Daten nach Schlüsseln sortiert speichert. Er kann binär sein, ist aber im Allgemeinen kein Binärbaum. Das Einfügen, Suchen und Löschen von Daten in B-Bäumen ist in amortisiert logarithmischer Zeit möglich. B-Bäume wachsen und schrumpfen, anders als viele Suchbäume, von den Blättern hin zur Wurzel. (de) B木（びーき、英:B-tree）は、計算機科学におけるデータ構造、特に木構造の一つ。ブロック単位のランダムアクセスが可能な補助記憶装置（ハードディスクドライブなど）上に木構造を実装するのに適した構造として知られる。 実システムでも多用されており、データベース管理システムの多くはB木による索引を実装している（B木の改良型または亜種であるB+木やB*木を使うことが多い）。 (ja) Ett B-träd är en datastruktur i form av ett balanserat . Varje nod har mellan m och m/2 barn, där m är ett givet heltal större än 1. Roten kan ha så få som 2 stycken n. Den här strukturen kan vara användbar om stora delar av trädet finns i långsammare minnen (som en hårddisk) eftersom trädets höjd kan reduceras genom att man väljer ett stort m. (sv) B树（英語：B-tree），是一种在计算机科学自平衡的树，能够保持数据有序。這種資料結構能夠讓查找數據、顺序访问、插入數據及刪除的動作，都在對數時間內完成。B树，概括来说是一个一般化的二元搜尋樹（binary search tree）一個節點可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。這種資料結構常被應用在数据库和文件系统的实现上。 (zh) B-strom je druh stromu. Je specifický tím, že má řád a limity na maximální, i minimální počet potomků vrcholu. B-strom je díky této vlastnosti vyvážený, operace přidání, vyjmutí i vyhledávání tedy probíhají v logaritmickém čase. Tato struktura je často používána v aplikacích, kdy není celá struktura uložena v operační paměti (RAM), ale v nějaké sekundární paměti, jako je pevný disk (například databáze). Protože přístup do tohoto typu paměti je náročný na čas (hlavně vyhledání náhodné položky), snažíme se minimalizovat počet přístupů do této paměti. (cs) En informatique, un arbre B (appelé aussi B-arbre par analogie au terme anglais « B-tree ») est une structure de données en arbre équilibré. Les arbres B sont principalement mis en œuvre dans les mécanismes de gestion de bases de données et de systèmes de fichiers. Ils stockent les données sous une forme triée et permettent une exécution des opérations d'insertion et de suppression en temps toujours logarithmique. (fr) Un B-albero (in inglese: B-tree) è una struttura dati che permette la rapida localizzazione dei file (record o chiavi), specie nelle basi di dati, riducendo il numero di volte che un utente necessita per accedere alla memoria in cui il dato è salvato. Essi derivano dagli alberi binari di ricerca, in quanto ogni chiave appartenente al sottoalbero sinistro di un nodo è di valore inferiore rispetto a ogni chiave appartenente ai sottoalberi alla sua destra; inoltre, la loro struttura ne garantisce il : per ogni nodo, le altezze dei sottoalberi destro e sinistro differiscono al più di una unità. Questo è il vantaggio principale del B-albero, e permette di compiere operazioni di inserimento, cancellazione e ricerca in tempi ammortizzati logaritmicamente. (it) 전산학에서 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효율적이다. B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있다. 대부분의 이진 트리는 항목이 삽입될 때 하향식으로 구성되는 데 반해, B-트리는 일반적으로 상향식으로 구성된다. n개의 키 (s1,s2,s3...,sn)가 있는 한 노드를 생각해 보자. 키집합은 정렬되어 있다고 한다. (즉, s1 B-트리는 노드 접근시간이 노드에서의 연산시간에 비해 훨씬 길 경우, 다른 구현 방식에 비해 상당한 이점을 가지고 있다. 이는 대부분의 노드가 하드디스크와 같은 에 있을 때 일반적으로 일어난다. 각 내부 노드에 있는 자식 노드의 수를 최대화함으로써, 트리의 높이는 감소하며, 균형맞춤은 덜 일어나고, 효율은 증가하게 된다. 대개 이 값은 각 노드가 완전한 하나의 디스크 블록 혹은 2차 저장장치에서의 유사한 크기를 차지하도록 정해진다. (ko) B-drzewo – drzewiasta struktura danych, przechowująca klucze w pewnym porządku i powiązane z nimi dane, używana przede wszystkim w systemach baz danych. Głównym pomysłem zastosowanym w B-drzewach jest struktura wewnętrznego węzła. Każdy węzeł może posiadać od do węzłów potomnych, gdzie to rząd B-drzewa; wyjątkiem jest korzeń, który może posiadać od do węzłów potomnych. Te założenia gwarantują, że wysokość drzewa zawierającego kluczy będzie niska, rzędu co też powoduje, że asymptotyczna złożoność czasowa operacji podstawowych: wyszukiwania, wstawiania i kasowania kluczy jest rzędu (pl) Em ciência da computação, uma árvore B é uma estrutura de dados em árvore, auto-balanceada, que armazena dados classificados e permite pesquisas, acesso sequencial, inserções e remoções em tempo logarítmico. A árvore B é uma generalização de uma árvore de pesquisa binária em que um nó pode ter mais que dois filhos. Diferente das árvores de pesquisa binária auto-balanceadas, a árvore B é bem adaptada para sistemas de armazenamento que leem e escrevem blocos de dados relativamente grandes, como discos. O que significa o B, se significa algo, nunca foi estabelecido. (pt) B-дерево (по-русски произносится как Би-дерево) — структура данных, дерево поиска. С точки зрения внешнего логического представления — сбалансированное, сильно ветвистое дерево. Часто используется для хранения данных во внешней памяти. Использование B-деревьев впервые было предложено Р. Бэйером (англ. R. Bayer) и Э. МакКрейтом (англ. E. McCreight) в 1970 году. Сбалансированность означает, что длины любых двух путей от корня до листьев различаются не более, чем на единицу. Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков. (ru) Б-дерева (англ. B-tree) — це один з видів збалансованих дерев, що забезпечують ефективне збереження інформації на магнітних дисках та інших пристроях з прямим доступом. Б-дерева схожі на червоно-чорні, різниця в тому, що в Б-дереві вузол може мати багато дітей, на практиці до тисячі, залежно від характеристик використовуваного диска. Завдяки цьому константа в оцінці O(log n) для висоти дерева менша, ніж для червоно-чорних дерев. Як і червоно-чорні дерева, Б-дерева дозволяють реалізувати багато операцій з множинами розміру n за час O(log n). (uk) |
| rdfs:label | B-tree (en) بي - تري (ar) Arbre-B (ca) B-strom (cs) B-Baum (de) Árbol-B (es) Arbre B (fr) B-albero (it) B 트리 (ko) B木 (ja) B-drzewo (pl) Árvore B (pt) B-дерево (ru) Б-дерево (uk) B-träd (sv) B树 (zh) |
| owl:differentFrom | dbr:Binary_tree dbr:B+-tree |
| owl:sameAs | freebase:B-tree wikidata:B-tree dbpedia-ar:B-tree dbpedia-az:B-tree dbpedia-ca:B-tree http://ckb.dbpedia.org/resource/درەختی_بی dbpedia-cs:B-tree dbpedia-de:B-tree dbpedia-es:B-tree dbpedia-fa:B-tree dbpedia-fr:B-tree dbpedia-he:B-tree dbpedia-hr:B-tree dbpedia-hu:B-tree dbpedia-it:B-tree dbpedia-ja:B-tree http://kn.dbpedia.org/resource/ಬಿ-ಟ್ರೀ dbpedia-ko:B-tree dbpedia-la:B-tree dbpedia-lmo:B-tree http://lt.dbpedia.org/resource/B-medis http://lv.dbpedia.org/resource/B_koks dbpedia-no:B-tree dbpedia-pl:B-tree dbpedia-pt:B-tree dbpedia-ru:B-tree dbpedia-sh:B-tree dbpedia-sr:B-tree dbpedia-sv:B-tree dbpedia-th:B-tree dbpedia-uk:B-tree dbpedia-vi:B-tree dbpedia-zh:B-tree https://global.dbpedia.org/id/4rTLo yago-res:B-tree |
| prov:wasDerivedFrom | wikipedia-en:B-tree?oldid=1123980396&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/B-tree.svg wiki-commons:Special:FilePath/B_tree_insertion_example.png |
| foaf:isPrimaryTopicOf | wikipedia-en:B-tree |
| is dbo:knownFor of | dbr:Rudolf_Bayer |
| is dbo:wikiPageDisambiguates of | dbr:B_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:B.tree dbr:B*-tree dbr:B-Tree dbr:Btree dbr:BTree dbr:B_Tree dbr:B_tree dbr:B_tree_indexing dbr:B*_tree dbr:B-star_tree dbr:B-trees dbr:Btrees dbr:Bayer_tree |
| is dbo:wikiPageWikiLink of | dbr:B.tree dbr:B_(disambiguation) dbr:Quarantine_(antivirus_program) dbr:Rudolf_Bayer dbr:Scapegoat_tree dbr:List_of_University_of_Illinois_Urbana-Champaign_people dbr:List_of_computer_scientists dbr:List_of_data_structures dbr:M-ary_tree dbr:M-tree dbr:Binary_search_algorithm dbr:Binary_search_tree dbr:Binary_tree dbr:Apple_File_System dbr:Best,_worst_and_average_case dbr:List_of_graph_theory_topics dbr:Patrick_O'Neil dbr:Perst dbr:Vectorwise dbr:Versant_Object_Database dbr:Index_locking dbr:Indexed_file dbr:InfinityDB dbr:Inode dbr:Interpolation_search dbr:T-tree dbr:(a,b)-tree dbr:Matthew_Dillon dbr:SQLite dbr:Order_statistic_tree dbr:Unrolled_linked_list dbr:R-tree dbr:Search_data_structure dbr:Timeline_of_algorithms dbr:Edward_M._McCreight dbr:MySQL dbr:NILFS dbr:NTFS dbr:Martin_Farach-Colton dbr:Ordered_Key-Value_Store dbr:Lightning_Memory-Mapped_Database dbr:MUMPS dbr:Cache-oblivious_algorithm dbr:Comparison_of_programming_languages_(associative_array) dbr:Comparison_of_relational_database_management_systems dbr:Personal_Storage_Table dbr:Surrogate_key dbr:Theoretical_computer_science dbr:MapReduce dbr:Michael_A._Bender dbr:B*-tree dbr:B+_tree dbr:B-Tree dbr:Btree dbr:Btrfs dbr:TokuDB dbr:TokuMX dbr:Tux3 dbr:Data_(computer_science) dbr:Data_structure dbr:Database_index dbr:Database_storage_structures dbr:Dissociated_press dbr:Distributed_file_system_for_cloud dbr:Fusion_tree dbr:HTree dbr:Hashed_array_tree dbr:K-D-B-tree dbr:2–3–4_tree dbr:Amazon_DynamoDB dbr:2–3_tree dbr:Database dbr:EXtremeDB dbr:Ext4 dbr:Extensible_Storage_Engine dbr:Fractal_tree_index dbr:Fractional_cascading dbr:Novell_Storage_Services dbr:Null_(SQL) dbr:Judy_array dbr:Tree_structure dbr:RDM_Server dbr:H2_(DBMS) dbr:HFS_Plus dbr:Hash_table dbr:Hierarchical_File_System dbr:Tarantool dbr:Technical_University_of_Munich dbr:Architecture_of_Btrieve dbr:AA_tree dbr:AVL_tree dbr:Bitmap_index dbr:Bitwise_trie_with_bitmap dbr:Block_Range_Index dbr:TUM_School_of_Computation,_Information_and_Technology dbr:Model_204 dbr:Red–black_tree dbr:MapR_FS dbr:Pick_operating_system dbr:PostgreSQL dbr:Splay_tree dbr:Free-space_bitmap dbr:Integer_sorting dbr:Metakit dbr:Michael_Stonebraker dbr:Microsoft_SQL_Server dbr:OrientDB dbr:R*-tree dbr:Raima_Database_Manager dbr:Mallard_BASIC dbr:Variety_(cybernetics) dbr:Z-order_curve dbr:Ext3 dbr:External_memory_algorithm dbr:ISAM dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Finger_search_tree dbr:Multiplicative_binary_search dbr:Self-balancing_binary_search_tree dbr:Semaphore_Corporation dbr:Priority_R-tree dbr:Reverse_index dbr:PH-tree dbr:Spatial_database dbr:BTree dbr:B_Tree dbr:B_tree dbr:B_tree_indexing dbr:B*_tree dbr:B-star_tree dbr:B-trees dbr:Btrees dbr:Bayer_tree |
| is dbp:badBlocksStruct of | dbr:HFS_Plus dbr:Hierarchical_File_System |
| is dbp:directoryStruct of | dbr:Apple_File_System dbr:Btrfs dbr:Tux3 dbr:HFS_Plus dbr:Hierarchical_File_System dbr:MapR_FS |
| is dbp:fileStruct of | dbr:NILFS dbr:Tux3 |
| is dbp:knownFor of | dbr:Rudolf_Bayer |
| is rdfs:seeAlso of | dbr:B+_tree |
| is owl:differentFrom of | dbr:Binary_tree |
| is foaf:primaryTopic of | wikipedia-en:B-tree |
