Partially persistent B-trees with constant worst-case update time

dc.contributor.author	Lagogiannis, G	en
dc.contributor.author	Lorentzos, N	en
dc.date.accessioned	2014-06-06T06:51:57Z
dc.date.available	2014-06-06T06:51:57Z
dc.date.issued	2012	en
dc.identifier.issn	00457906	en
dc.identifier.uri	http://dx.doi.org/10.1016/j.compeleceng.2011.12.009	en
dc.identifier.uri	http://62.217.125.90/xmlui/handle/123456789/5788
dc.subject.other	Asymptotically optimal	en
dc.subject.other	B trees	en
dc.subject.other	Constant time	en
dc.subject.other	General approach	en
dc.subject.other	General method	en
dc.subject.other	I/O-complexity	en
dc.subject.other	Secondary memories	en
dc.subject.other	Specific problems	en
dc.subject.other	Data structures	en
dc.subject.other	Forestry	en
dc.subject.other	Algorithms	en
dc.subject.other	Data Bases	en
dc.subject.other	Forestry	en
dc.subject.other	Problem Solving	en
dc.title	Partially persistent B-trees with constant worst-case update time	en
heal.type	journalArticle	en
heal.identifier.primary	10.1016/j.compeleceng.2011.12.009	en
heal.publicationDate	2012	en
heal.abstract	We present two solutions for achieving a partially persistent B-tree with a worst case constant update time, in the case that the position of the update is given. The motivation for this work came from the observation that a known, general approach, which reduces the update cost of partially persistent data structures to a constant, has an inherent weakness concerning partially persistent B-trees, because it creates big nodes that cannot be retrieved from secondary memory in a constant time. Due to this, the I/O complexity of the resulting partially persistent B-tree is affected. Thus, we attack this specific problem, i.e. we do not develop a general approach for all partially persistent data structures. For our objectives, we add partial persistence to an ephemeral B-tree with constant worst case update time, by applying two known general methods, the fat-node and the node-copying method, that transform an ephemeral data structure into a partially persistent. The solution based on node-copying is asymptotically optimal. © 2011 Elsevier Ltd. All rights reserved.	en
heal.journalName	Computers and Electrical Engineering	en
dc.identifier.issue	2	en
dc.identifier.volume	38	en
dc.identifier.doi	10.1016/j.compeleceng.2011.12.009	en
dc.identifier.spage	231	en
dc.identifier.epage	242	en