0%

我们将表的格式从未排序的行数组更改为 B 树。这是一个很大的改动,需要多篇文章来实现。在本文的结尾,我们将定义叶节点的布局,并支持将键/值对插入到单节点树中。但首先,让我们回顾一下切换到树结构的原因。

替代表格格式

使用当前格式,每个页面仅存储行(无元数据),因此非常节省空间。插入也很快速,因为我们只需追加到末尾即可。但是,只能通过扫描整个表来查找特定行。如果要删除一行,则必须通过移动其后的每一行来填补该空缺。

如果我们将表存储为数组,但按 id 对行进行排序,则可以使用二分查找来查找特定 id。但是,插入会很慢,因为我们必须移动很多行来腾出空间。

相反,我们采用树结构。树中的每个节点可以包含可变数量的行,因此我们必须在每个节点中存储一些信息以跟踪其包含的行数。此外,还有所有不存储任何行的内部节点的存储开销。作为交换,虽然数据库文件变大了,但我们获得了快速的插入、删除和查找功能。

未排序的行数组 已排序的行数组 节点树
页面包含 仅数据 仅数据 元数据、主键和数据
每页行数 更多的 更多的 更少
插入 O(1) O(n) O(log(n))
删除 O(n) O(n) O(log(n))
通过id查找 O(n) O(log(n)) O(log(n))
Read more »

B-Tree是 SQLite 用来表示表和索引的数据结构,因此它是一个非常核心的思想。本文只是介绍数据结构,所以不会有任何代码。

为什么树是数据库的良好数据结构?

  • 搜索特定值很快(对数时间)
  • 插入/删除您已经找到的值速度很快(重新平衡的时间很长)
  • 遍历一系列值的速度很快(与哈希映射不同)

B 树与二叉树不同(“B”可能代表发明者的名字,但也可以代表“平衡”)。这是一个 B 树示例:

example B-Tree (https://en.wikipedia.org/wiki/File:B-tree.svg)

与二叉树不同,B 树中的每个节点可以有 2 个以上的子节点。每个节点最多可以有 m 个子节点,其中 m 称为树的“order”。为了保持树基本平衡,我们还说节点必须至少有 m/2 个子节点(向上舍入)。

Read more »

安装

1
curl https://sh.rustup.rs -sSf | sh

安装完成后

1
Rust is installed now. Great!

快速参考

Read more »

读书时听着老师念答案不太能读懂诗词,年纪大了便能体会到其中的韵味和阅历。每次读时,还能有不同的品味。

诗词包含了古人所有的情感,你的酸甜苦辣,各种感受都能从中找到共鸣。

定风波·莫听穿林打叶声

苏轼

三月七日,沙湖道中遇雨,雨具先去,同行皆狼狈,余独不觉。已而遂晴,故作此词。

莫听穿林打叶声,何妨吟啸且徐行。竹杖芒鞋轻胜马,谁怕?一蓑烟雨任平生。

料峭春风吹酒醒,微冷,山头斜照却相迎。回首向来萧瑟处,归去,也无风雨也无晴。

Read more »

当测试程序需要数据时,可以通过faker来构造测试数据

安装

1
$ pip install faker

基本使用

1
2
3
4
5
6
7
8
9
10
11
12
from faker import Faker
faker = Faker()

faker.name()
# 'Lucy Cechtelar'

faker.address()
# '426 Jordy Lodge
# Cartwrightshire, SC 88120-6700'

faker.ipv4()
# '196.67.103.129'

对方法 faker.ipv4()的每次调用都会产生不同的随机结果

1
2
3
4
5
6
7
8
9
10
11
12
13
for _ in range(10):
print(faker.ipv4())

# '120.36.235.152'
# '16.58.6.69'
# '170.215.56.41'
# '135.217.158.192'
# '218.235.87.38'
# '175.80.75.73'
# '122.120.1.128'
# '99.91.143.38'
# '1.90.129.142'
# '184.148.193.249'
Read more »

Steve Jobs

I am honored to be with you today at your commencement from one of the finest universities in the world. Truth be told, I never graduated from college, and this is the closest I’ve ever gotten to a college graduation. Today I want to tell you three stories from my life. That’s it. No big deal. Just three stories.

The first story is about connecting the dots.

I dropped out of Reed College after the first 6 months, but then stayed around as a drop-in for another 18 months or so before I really quit. So why did I drop out?

It started before I was born. My biological mother was a young, unwed college graduate student, and she decided to put me up for adoption. She felt very strongly that I should be adopted by college graduates, so everything was all set for me to be adopted at birth by a lawyer and his wife. Except that when I popped out they decided at the last minute that they really wanted a girl.

Read more »

ACT I

Dialogue

Excuse me. My name is Richard Stewart.

I’m a photographer.
May I take a picture of you and your little boy?

What’s it for?

It’s for a book.

You’re writing a book?

It’s a book of pictures.

I call it Family Album, U.S.A.

Read more »

1. 概述

Protocol Buffers(又名protobuf) 是一种语言中立、平台中立的可扩展机制,用于序列化结构化的数据

它就像JSON,只是它更小、更快

只需定义一次数据如何被结构化,然后就可以使用特殊生成的源代码,轻松地从各种数据流和使用各种语言写入和读取结构化数据

Read more »

On August 28, 1963, some 100 years after President Abraham Lincoln signed the Emancipation Proclamation freeing the slaves, a young man named Martin Luther King climbed the marble steps of the Lincoln Memorial in Washington, D.C. to describe his vision of America. More than 200,000 people-black and white-came to listen. They came by plane, by car, by bus, by train, and by foot. They came to Washington to demand equal rights for black people. And the dream that they heard on the steps of the Monument became the dream of a generation.

As far as black Americans were concerned, the nation’s response to Brown was agonizingly slow, and neither state legislatures nor the Congress seemed willing to help their cause along. Finally, President John F. Kennedy recognized that only a strong civil rights bill would put teeth into the drive to secure equal protection of the laws for African Americans. On June 11, 1963, he proposed such a bill to Congress, asking for legislation that would provide “the kind of equality of treatment which we would want for ourselves.” Southern representatives in Congress managed to block the bill in committee, and civil rights leaders sought some way to build political momentum behind the measure.

A. Philip Randolph, a labor leader and longtime civil rights activist, called for a massive march on Washington to dramatize the issue. He welcomed the participation of white groups as well as black in order to demonstrate the multiracial backing for civil rights. The various elements of the civil rights movement, many of which had been wary of one another, agreed to participate. The National Association for the Advancement of Colored People, the Congress of Racial Equality, the Southern Christian Leadership Conference, the Student Non-violent Coordinating Committee and the Urban League all managed to bury their differences and work together. The leaders even agreed to tone down the rhetoric of some of the more militant activists for the sake of unity, and they worked closely with the Kennedy administration, which hoped the march would, in fact, lead to passage of the civil rights bill.

Read more »

简介

tcpdump是一个命令行数据包分析、抓取工具

可以使用 -D 标志来列出可用于捕获的接口

1
2
3
4
5
6
7
8
9
10
11
$ tcpdump -D

1.virbr0
2.docker0
3.vethdb0f731
4.nflog (Linux netfilter log (NFLOG) interface)
5.nfqueue (Linux netfilter queue (NFQUEUE) interface)
6.usbmon1 (USB bus number 1)
7.enp2s0
8.usbmon2 (USB bus number 2)
9.enp3s0

可以使用 -i 标志指定要捕获的接口,指定 any 作为接口将从所有活动接口捕获

1
2
$ tcpdump -i any
$ tcpdump -i eth1

可以使用 -v 标志来调整tcpdump输出中的详细程度

1
2
3
$ tcpdump -i any -v (Verbose output)
$ tcpdump -i any -vv (Even more verbose output)
$ tcpdump -i any -vvv (The most verbose output)
Read more »