Batina's Blog

[c++/STL] sort, stable_sort, partial_sort, nth_element

这次我们来讲讲 C++/STL 里的排序算法。最后混进来的 nth_element 是选择算法，以$O(n)$的平均时间复杂度返回第 n 小的元素（若有重复元素则是排序后 n-th 位置上的元素...

Posted by Dongbo on January 1, 2022

[年终总结] 再见，2021

年终报告快轮到我了，到底还是没法静下心看代码，趁这个时间把2021的年度总结起个头吧。 以前我从来没想过要做年度总结的，看到别人的博客、朋友圈和空间里年末或者年初时发的总结总感觉无聊和浪费时间...

Posted by Dongbo on December 30, 2021

[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