| title | tags | created | modified | |||
|---|---|---|---|---|---|---|
algs-tree-btree |
|
2023-04-20 08:12:41 UTC |
2023-09-17 18:17:41 UTC |
-
who is using #b-tree
- postgresql
- sqlite
- foundationdb
- loro-crdt
- bonsaidb/nebari
-
who is using #b+tree
- mongodb
- couchdb
- couchstore-legacy
-
foundationdb
- v7_202112: First release of the Redwood Storage Engine, a BTree storage engine with higher throughput and lower write amplification than SQLite.
-
redis
- Redis Internal Data Structure : Skiplist, sds/Simple Dynamic Strings, dictionary, adlist/Doubly Linked List
- Skip List gets O(log n) time complexity on average. And it is easy to implement compared to AVL tree or Red-Black tree. So Redis uses it to implement ordered set.
- Redis provides SDS because it supports efficient functions to get the string length and append another string to the end without allocating memory each time.
- dictionary is implemented by means of hash table and there are two hash tables in dictionary to implement incremental rehashing.
- Redis Internal Data Structure : Skiplist, sds/Simple Dynamic Strings, dictionary, adlist/Doubly Linked List
-
resources
- https://github.com/postgres/postgres/tree/master/src/backend/access/nbtree /clang
- This directory contains a correct implementation of Lehman and Yao's high-concurrency B-tree management algorithm
This piece not only describes how B-trees and database indexes work, but gives you the opportunity to interact with them
- Hackreels 这个动画效果真不错