Batina's Blog

[db/BoltDB] 4 - FreeList

上回我们说到，BoltDB 中删除元素之后，得到的空闲页面并不会归还给操作系统，因此它的数据库文件只增不减。但是从逻辑上来说我们肯定不能白占着资源不干活，BoltDB 也不会一直闲置这些空闲页面...

Posted by Dongbo on December 29, 2021

[db/BoltDB] 3 - Indexing: B+ Tree

上次我们在 BoltDB Transaction 中简略介绍了 BoltDB B+树索引的实现，但是有些细节没有具体介绍。本文就来结合代码详细归纳一下 BoltDB 如何用短短 400 多行代码...

Posted by Dongbo on December 29, 2021

[db/BoltDB] 2 - BoltDB Transaction

本篇将介绍 BoltDB 事务的实现。本来看到 etcd 中有 MVCC 机制，还以为是底层存储的 BoltDB 本身的 MVCC 机制。没想到其实 etcd 的 MVCC 是使用 BoltDB...

Posted by Dongbo on December 28, 2021

[db/BoltDB] 1 - Introduction

BoltDB是golang实现的一个kv-store，据说etcd的底层存储用的是它。这里打算做个简短的系列从源码层面学习一下事务的实现。说起来在这之前我甚至都不知道什么叫嵌入式数据库，后来搜了...

Posted by Dongbo on December 27, 2021

[go/Solution] 循环依赖和解决笔记

重构项目的时候，费劲巴拉的把一堆冗余的switch case拆开到一个个单独的go文件里了，结果编译的时候出现了import cycle not allowed。 项目里一大堆目录看着烦得要死...

Posted by Dongbo on December 2, 2021

[B+ Tree] 3 - B+树并发

我们知道数据库的事务通过一系列并发控制手段能够保证并发执行的事务操作数据时不会互相干扰，而索引作为事务执行时需要经常访问的数据结构，我们也需要考虑使用并发控制措施来保证多线程同步访问索引结构时不...

Posted by Dongbo on September 30, 2021

[B+ Tree] 2 - B+树的插入/删除

我们终于要开始介绍B+树和它的基本操作了。这里我们将以 15-445 fall 2020 project2 的实现思路为模板介绍 B+ 树的结构，以图文的形式介绍插入、删除操作以及对应的调整操作...

Posted by Dongbo on September 30, 2021

[B+ Tree] 1 - B+树应用场景

做完了cmu 15-445 2020的project之后，想着稍微归纳一下从这个项目里学到的东西，这个项目总共完成了缓存管理、b+树索引、executor、transaction mana...

Posted by Dongbo on September 30, 2021

[algo/hash] 加密哈希与非加密哈希

之前大概知道MD5和SHA-1/SHA-2都是某种哈希算法，但是看了实现感觉跟数据结构课上学到的哈希函数不是同一个东西，最近才知道哈希算法分为加密/非加密哈希，故挖此坑。（另外之前略微了解...

Posted by Dongbo on June 17, 2021

[AVL Tree] 1 - 从二叉搜索树到平衡二叉搜索树

曾经上数据结构的时候上机作业留过一道AVL树的题目，班上有个搞ACM的大佬花了一个下午的时间写完了，当时我听到居然要写两百多行代码简直佩服得五体投地并且放弃了自己写的打算，对AVL树的理解...

Posted by Dongbo on April 24, 2021