/
btrees.html
70 lines (53 loc) · 2.88 KB
/
btrees.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
title = B-Tree resources
---
<p>
[Open a
PR](https://github.com/eatonphil/eatonphil.com/blob/main/home/posts/btrees.html)
if you've got a resource you think might fit in.
</p>
### Visualization
<ul>
<li>[BTrees](https://www.cs.usfca.edu/~galles/visualization/BTree.html) from USFCA </li>
<li>[B-Trees](https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/BTree.html) from OpenDSA</li>
</ul>
### Descriptions
<ul>
<li>[B-Trees (Pseudocode)](https://opendatastructures.org/ods-python/14_2_B_Trees.html) from Open Data Structures</li>
<li>[B-Trees (C++)](https://opendatastructures.org/ods-cpp/14_2_B_Trees.html) from Open Data Structures</li>
<li>[Insertion Into a B-Tree](https://webdocs.cs.ualberta.ca/~holte/T26/ins-b-tree.html) from UAlberta</li>
<li>[B Trees](https://sites.radford.edu/~nokie/classes/360/trees.b.tree.html) from Radford University</li>
<li>[The Ubiquitous B-Tree (1979)](https://carlosproal.com/ir/papers/p121-comer.pdf) from Purdue University</li>
<li>[Database Internals (2019)](https://www.databass.dev/) by Alex Petrov</li>
<li>[B-trees](https://shachaf.net/w/b-trees) by Shachaf Ben-Kiki</li>
<li>[Evolution of b-tree data structures for indexing](https://erthalion.info/2020/11/28/evolution-of-btree-index-am/) by Dmitry Dolgov</li>
</ul>
### Extensions
<ul>
<li>[Closing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware with Built-in Transparent Compression (2022)](https://www.usenix.org/conference/fast22/presentation/qiao)</li>
<li>[The Bw-Tree: A B-tree for New Hardware Platforms (2017)](https://15721.courses.cs.cmu.edu/spring2017/papers/08-oltpindexes2/bwtree-icde2013.pdf)</li>
<li>[An Introduction to Bε-trees and Write-Optimization (2015)](http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf)</li>
</ul>
### Array Layouts
<ul>
<li>[Array Layouts for Comparison-Based Searching](https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf)</li>
<li>[Eytzinger Binary Search](https://algorithmica.org/en/eytzinger)</li>
<li>[Implicit Static B-Trees](https://algorithmica.org/en/b-tree)</li>
</ul>
### Surveys & Design Space
<ul>
<li>[Modern B-Tree Techniques (2011)](https://w6113.github.io/files/papers/btreesurvey-graefe.pdf) by Goetz Graefe</li>
</ul>
### Comparison & Critique
<ul>
<li>[Btree vs LSM](https://github.com/wiredtiger/wiredtiger/wiki/Btree-vs-LSM) by MongoDB</li>
</ul>
### Implementations & Discussion
<ul>
<li>[Rust Collections Case Study: BTreeMap](https://cglab.ca/~abeinges/blah/rust-btree-case/)</li>
<li>[B-tree Ordered Containers (2019)](https://abseil.io/blog/20190812-btree) from Abseil</li>
<li>[C++ containers that save memory and time (2013)](https://opensource.googleblog.com/2013/01/c-containers-that-save-memory-and-time.html) from Google</li>
</ul>
### Guided Implementation
<ul>
<li>[CMU Database Systems B+ Tree Project](https://15445.courses.cs.cmu.edu/spring2023/project2/)</li>
</ul>