About: Fractal tree index

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Fractal tree index Goto Sponge NotDistinct Permalink

An Entity of Type : yago:WikicatDatabaseIndexTechniques, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FFractal_tree_index&graph=http%3A%2F%2Fdbpedia.org&graph=http%3A%2F%2Fdbpedia.org

In computer science, a fractal tree index is a tree data structure that keeps data sorted and allows searches and sequential access in the same time as a B-tree but with insertions and deletions that are asymptotically faster than a B-tree. Like a B-tree, a fractal tree index is a generalization of a binary search tree in that a node can have more than two children. Furthermore, unlike a B-tree, a fractal tree index has buffers at each node, which allow insertions, deletions and other changes to be stored in intermediate locations. The goal of the buffers is to schedule disk writes so that each write performs a large amount of useful work, thereby avoiding the worst-case performance of B-trees, in which each disk write may change a small amount of data on disk. Like a B-tree, fractal tree

Attributes	Values
rdf:type	yago:Ability105616246 yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:Know-how105616786 yago:Method105660268 yago:PsychologicalFeature100023100 building yago:Structure105726345 yago:Technique105665146 yago:WikicatDatabaseIndexTechniques
rdfs:label	Fractal tree index (en)
rdfs:comment	In computer science, a fractal tree index is a tree data structure that keeps data sorted and allows searches and sequential access in the same time as a B-tree but with insertions and deletions that are asymptotically faster than a B-tree. Like a B-tree, a fractal tree index is a generalization of a binary search tree in that a node can have more than two children. Furthermore, unlike a B-tree, a fractal tree index has buffers at each node, which allow insertions, deletions and other changes to be stored in intermediate locations. The goal of the buffers is to schedule disk writes so that each write performs a large amount of useful work, thereby avoiding the worst-case performance of B-trees, in which each disk write may change a small amount of data on disk. Like a B-tree, fractal tree (en)
name	Fractal tree index (en)
dcterms:subject	Trees (data structures) Database index techniques
Wikipage page ID	41058483 (xsd:integer)
Wikipage revision ID	1096094741 (xsd:integer)
Link from a Wikipage to another Wikipage	Binary search tree Upsert Open source Branching factor MongoDB MySQL Martin Farach-Colton Tree data structure Subtree Computer science Michael A. Bender B-tree TokuDB TokuMX Leaf node Log-structured merge-tree ACID Database Trees (data structures) Database index techniques MariaDB External memory algorithm Search tree Filesystem Tokutek Bloom filters
sameAs	Fractal tree index Fractal tree index Fractal tree index Fractal tree index Fractal tree index
dbp:wikiPageUsesTemplate	dbt:COI dbt:CS-Trees dbt:Math dbt:Multiple_issues dbt:Notability dbt:Reflist dbt:Data_structures dbt:Infobox_data_structure
type	tree (en)
has abstract	In computer science, a fractal tree index is a tree data structure that keeps data sorted and allows searches and sequential access in the same time as a B-tree but with insertions and deletions that are asymptotically faster than a B-tree. Like a B-tree, a fractal tree index is a generalization of a binary search tree in that a node can have more than two children. Furthermore, unlike a B-tree, a fractal tree index has buffers at each node, which allow insertions, deletions and other changes to be stored in intermediate locations. The goal of the buffers is to schedule disk writes so that each write performs a large amount of useful work, thereby avoiding the worst-case performance of B-trees, in which each disk write may change a small amount of data on disk. Like a B-tree, fractal tree indexes are optimized for systems that read and write large blocks of data. The fractal tree index has been commercialized in databases by Tokutek. Originally, it was implemented as a cache-oblivious lookahead array, but the current implementation is an extension of the Bε tree. The Bε is related to the Buffered Repository Tree. The Buffered Repository Tree has degree 2, whereas the Bε tree has degree Bε. The fractal tree index has also been used in a prototype filesystem. An open source implementation of the fractal tree index is available, which demonstrates the implementation details outlined below. (en)
invented by	Michael A. Bender, Martin Farach-Colton, Bradley C. Kuszmaul (en)
invented year	2007 (xsd:integer)
gold:hypernym	Structure
prov:wasDerivedFrom	wikipedia-en:Fractal_tree_index?oldid=1096094741&ns=0
page length (characters) of wiki page	17930 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Fractal_tree_index
is Link from a Wikipage to another Wikipage of	Martin Farach-Colton Michael A. Bender TokuDB TokuMX Document-oriented database OrientDB Fractal Tree index
is Wikipage redirect of	Fractal Tree index
is foaf:primaryTopic of	wikipedia-en:Fractal_tree_index

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 50 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software