GreenHatHGのBlog

单线程版 B+树插入操作 Overview Index: The index in database system is responsible for fast data retrieval without having to search through every row in a database table, providing the basis for both rapid random lookups (快速随机查找) and efficient access of ordered records. B+Tree dynamic index structure: It is a balanced tree in which the internal pages direct the search and leaf pages contains actual data entries.B+ Tree properties Each node except root can have a maximum of M children and at least ce...

Buffer PoolDisk-Oriented DBMS什么是buffer pool，buffer pool有什么用（针对Disk-Oriented DBMS） The database is all on disk, and the data in the database files is organized into pages. In order to operate on the data the DBMS needs to bring the data into memory. It does this by having a buffer pool that manages the movement back and forth between disk and memory. The DBMS also have an execution engine that will execute queries. The execution engine will ask the buffer pool for a specific page, and the...

https://15445.courses.cs.cmu.edu/fall2022/project1/ DB的Buffer Replacement Policies中的LRU和Clock算法都容易受到sequential flooding的影响，对于LRU来讲，使用LRU-K算法能够缓解这个问题。 LRU-K This component is responsible for tracking page usage in the buffer pool. The LRU-K algorithm evicts a frame whose backward k-distance is maximum of all frames in the replacer. Backward k-distance is computed as the difference in time between current timestamp and the timestamp of kth previous access. A frame with less than k historical ac...

前提：搞懂https://www.geeksforgeeks.org/extendible-hashing-dynamic-approach-to-dbms/ Whyhttps://15445.courses.cs.cmu.edu/fall2022/project1/ 待补充，可看原论文设计要点： Page Fault Access Memory/Disk Dynamic File Organization Balance Radix Search Tree Static & Dynamic Hash Concepts $h$: fixed hash function $K$: is a key $K’$: $h(K)$, also $pseudokey$. We choose pseudokeys to be of fixed length, such as 32 bits. The pseudokeys are of fixed length, the keys need not be. $I(K)$: is associated information:...

背景 链接：https://15445.courses.cs.cmu.edu/fall2022/project0/ 目的：因为后续的项目都是使用c++编写，所以提供一个入门c++项目给新手熟悉下。 要求：给出基本的代码框架，填充核心代码实现trie树的插入、查找、删除。最终要求为并发版本，但是不要求性能，所以可以一把大锁直接梭哈。 环境：使用clang-12，c++17标准 使用到的常见cpp知识点： unique_ptr管理内存资源 类的常见知识，比如构造函数，类方法等 rvalue与move shared_mutex trie树简单记录下trie树 作用又称前缀树或字典树，存储公共前缀字符串比较高效，一般用于字符串查找。 在项目中的应用是将(key, value)插入到trie树，类似hashmap的作用，但是使用trie树实现。 普通的trie树如下： 项目中要求实现的trie树： 上面是将(ab, 1)和(ac, “val”)插入到trie。注意项目中的value都是同类型的，这里是不同类型 结构给出的代码框架中总共有三个类 TrieNode：除了带有valu...

17-Virtual-Memory-ConceptsPhysical and Virtual Addressing Main memory: an array of M contiguous(连续的) byte-size cells(单元). Each byte has a unique physical address (PA) {0, 1, 2, 3 … } The most natural way for a CPU to access memory would be to use physical addresses. We call this approach physical addressing. When the CPU executes the load instruction, it generates an effective physical address and passes it to main memory over the memory bus. The main memory fetches the 4-byte wor...

18-Virtual-Memory-SystemsSimple memory system exampleAddress Translation Example #1 PPN实际不存在页表中 MMU做的第一件事是检查TLB，将VA中的VPN的TLBI(0x3)和TLBT(0x03)提取出来。所以会去查set3找到tag为3的line，找到对应的line并且valid为1，TLB将PPN(0D)返回给MMU MMU使用0D构建物理地址。将VA的VPO复制到PA的PPO，0D作为PA的PPN，由此构成了一个物理地址 将地址发送给cache，提取出CI(0x5)、CT(0x0D)，所以会去查set5找到tag为0xD的line，找到并且valid为1，因为CO为0，所以找到B0(36) cache将该字节通过MMU返回给CPU，并将其存到一个寄存器中。 Address Translation Example #2 VA中的VPN的TLBI=TLBT=0，TLB的set=0&tag=0的line的valid=0，TLB miss 通过VPN=0查找页表，valid=1有效，...

玩客云捡垃圾，40块钱还行，民间大佬弄出了刷Linux的方法，可惜是32位，不过也凑合用，比斐讯N1折腾了那么一点。 beancountbeancount介绍可以看下面几个文章，整挺好。之前是用ios端的Moze3，感觉还是差了点意思。 Beancount复式记账（一）：为什么 复式记账指北（三）：如何打造不半途而废的记账方案 使用 Beancount 管理家庭财务 · 构建我的被动收入 使用 Costflow 提高 Beancount 记账效率 bot-docker这里推荐使用kaaass/beancount_bot_costflow_docker，参考上面第二篇文章，里面有详细说明。不过上面的镜像只支持64位，只能自己弄32位的docker镜像。 Dockerfile从beancount_bot_costflow_docker的Dockerfile修改而来 12345678910111213141516171819202122232425262728FROM alpine:3.6WORKDIR /appADD requirements.txt /appENV PYTHONU...

来源：https://www.ardanlabs.com/blog/2019/05/garbage-collection-in-go-part2-gctraces.html 开关GC的对比有一个从不同的新闻提供商下载RSS并搜索的应用程序 在关闭GC的情况下测试并发请求应用程序耗时情况 12345$ go build$ GOGC=off ./project > /dev/null# 10k requests using 100 connectionshey -m POST -c 100 -n 10000 "http://localhost:5000/search?term=topic&cnn=on&bbc=on&nyt=on" 处理10k个请求需要4188ms，每秒处理约2387个请求 在开启GC的情况下呢， 123456$ GODEBUG=gctrace=1 ./project > /dev/nullgc 3 @3.182s 0%: 0.015+0.59+0.096 ms clock, 0.19+0.10/1.3/3.0...

来源：https://go.dev/talks/2012/concurrency.slide The boring function runs, like a boring party guest. 12345678910111213func boring(msg string) { for i := 0; ; i++ { fmt.Println(msg, i) time.Sleep(time.Duration(rand.Intn(1e3)) * time.Millisecond) }}func main() { go boring("boring!") fmt.Println("I'm listening.") time.Sleep(2 * time.Second) fmt.Println("You're boring; I'm leaving.")} A channel connects the main and bor...