Skip to content
This repository has been archived by the owner. It is now read-only.
Evaluation of several different b-trees with regard to lock contention
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.


This is the repo for our databases class project. Our report is in report.pdf.

We modify the concurrent B-tree with OLC from


> git clone
> cd hot-spots
> git submodule update --init --recursive
> make

You need to have g++ 7 or newer, along with GNU make.

To run tests for B-tree implementations: make tst.all. To run a test foo: make foo.tst.

To build the report: make report.pdf.

Running workloads

All benchmarks were run using the benchmarks/ script in this repo. It allows varying the number of insertion and lookup threads, the B-tree implementation, and the number of operations per thread, the initial load of the B-tree, and the frequency with which to output statistics. See the usage message for more info:

> cd benchmarks
> bash # prints help message

To run benchmarks, you need to have passwordless sudo access. You also need to have cpupower installed. To get this tool, install apt install linux-tools-common. Then, attempt to run cpupower. This will fail with a message that tells you what else to install (it is kernel-specific). Install the first package only.

Plotting graphs

The results of the workloads are produced in the results directory. To graph results, use the results/ script. The figures in the figures directory were generated using this script. See the usage message for more info:

> ./ # prints the help message

This script requires python 3, numpy, and matplotlib.


The organization of this repository is as follows:

  • This README.
  • makefile: The makefile for building and running everything.
  • benchmarks/: Implementation of benchmarks and utilities for running.
  • btrees/: Implementation of B-trees.
  • figures/: Figures produced from results with the script.
  • results/: Results produced from the script.
  • tests/: Correctness tests for the B-trees.
  • report.tex, references.bib: Our report.
You can’t perform that action at this time.