Random B-Trees With Inserts and Deletes (Classic Reprint)

T. Johnson, D. Shasha

ISBN 10: 133314301X / ISBN 13: 9781333143015

Published by Forgotten Books, 2018

About this Item

Print on Demand. This book analyzes how the utilization of B-tree nodes under mixed insert and delete operations affects the number of levels in a B-tree and its performance. It derives analytical and simulational equations for the utilization of B-trees constructed from a mixture of insert and delete operations. The author shows that the utilization is 39% when the number of inserts is the same as the number of deletes. However, if there are just 5% more inserts than deletes, the utilization is over 62%. The book calculates the probabilities of splitting and merging, presenting a simple rule-of-thumb to estimate the probability of splitting accurately. The book also models B-trees that merge half-empty nodes and compares them to B-trees that merge empty nodes. This book will be of interest to database management system designers and users. This book is a reproduction of an important historical work, digitally reconstructed using state-of-the-art technology to preserve the original format. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in the book.

Seller Inventory # 9781333143015_0

Bibliographic Details

• Title: Random B-Trees With Inserts and Deletes (Classic Reprint)
• Publisher: Forgotten Books
• Publication Date: 2018
• Language: English
• ISBN 10: 133314301X
• ISBN 13: 9781333143015
• Binding: Paperback
• Condition: New
• Book Type: print-on-demand item
• Seller catalogs:
  • Statistics

About this title

Synopsis

Understand how B-trees behave under mixed inserts and deletes. This detailed study guides readers through analytical models and simulations that predict how much of a B-tree remains utilized, how often nodes split or merge, and what the height of the tree might look like under different operation mixes.

The book examines two main B-tree variants and compares their performance in realistic workloads. It explains how ghosts (deleted items still affecting structure) are modeled and how different strategies impact space utilization and restructuring rates.

• Clear explanations of equilibrium structures and utilization under parameterized insert/delete mixes


• Two B-tree variants: merge-at-empty and merge-at-half, with comparisons to real-world behavior


• Simulation results that validate analytical predictions about splits, merges, and height

Ideal for readers of database systems, data structures, and performance modeling who want a rigorous, math‑driven look at B-trees in dynamic workloads.