为什么用Btree

Flash、NVM之类的新型存储器的出现,对数据库技术产生了颠覆性的革命。于是我决定从头好好学学数据库理论,以寻找它究竟在哪些方面产生了颠覆性的改革。

题外话:今天有个朋友问我,如何在内存中高效的组织和索引数据。我立马就想到了btree,被否。我想到Hash。再被否,从btree泛化到一般的m路平衡查找树。再被否,我无奈了。事后我不得不承认,一个人的思维广度,他的阅历以及内功是决定性的。后来我仔细想想,对于大部分数据都cache在内存中的情况而言,btree的确不是最优选择,红黑树应该远胜于它。

Btree的出现,是因为需要在硬盘上检索数据。它对硬盘的理解是:

1、基于块(通常是512字节)的方式访问。

2、支持随机读写。

3、访问延迟高。大约是内存访问延迟的10万倍以上。

4、传输带宽小。大约是内存的千分之一左右。

Btree的核心思想是,每次查找所需的IO次数基本是常量并且尽可能的小。拿Berkeley DB做例子,每个Node是一个(或几个)Page,Node被分为两种,Leaf Node和Internal Node。Internal Node只用来查找,所以可以称为索引节点,而value都在Leaf Node上,所以Leaf Node也可称为数据节点。Btree是平衡树,就意味着任何两个节点到Root Node的距离基本相等(最多相差1),从这一点保证了每次查找所需的IO次数基本是常量。而为了IO次数尽可能的小,就要控制树的高度,所以才用了m路的方式,即它不是一个二叉树也不是三叉数,而是一个m叉树。m通常很大,所以高度一般都在5以内。

继续拿Berkeley DB分析,来估算m最大是多少。它的每个page都有一个唯一整数来标识,且称为page id。那么单表理论上限=2 ^ (sizeof(page id)*8) * pagesize,一般来说,page id是32位整数,那么就是16TB。今天那个朋友质疑我,你用32位来存这个是不是太浪费了?因为他的情况是,实际要存的value也不过是一个32位整数。那么好,假如page id是16位,那么上式的结果是256MB,我相信对于大多数应用都是不能忍的。

(这些数据都是我笔算的,而不是从网上找来的。我一直怀疑我会不会哪步算错了。如果你发现了,请告诉我)

缩短page id的长度,无非是希望索引页能存更多的key。每个页面的key的最大个数=(pageSize-pageHeaderSize)/(keysize+sizeof(page id))。以游戏为例,通常拿roleid作为key。如果keysize=4,那么每页最多500个key。如果keysize=8,那么每页最多330个key。btree的最大高度的计算公式是: ln( (n + 1)/2 )/ln(m),其中n是整个数据集的大小,m是每个页面能存多少key。就游戏来说,如果单台服务器角色数量在1千万之内,那么btree的高度不会大于3层。但是就Berkeley DB而言,因为它是一个通用数据库,key未必是定长整数,所以它实际上keysize=original keysize+5。无论如何,btree体现出来的优势是,即便数据集规模很大,几千亿条,也可以在5次IO内检索到数据。

假设完全没有cache,那么每次查找所花的IO时间大约为h*(寻道时间+旋转延迟+pagesize/传输带宽)。把上面式子代入进来,就是ln(n/2)*(寻道时间+旋转延迟+pagesize/传输带宽)/(ln(pageSize-pageHeaderSize)-ln(keysize+sizeof(page id)))。我现在没时间去解这个函数的最优值,反正可以看出,根据寻道时间、旋转延迟、传输带宽、keysize来适当的选择pagesize,可以有效的提高IO效率。一个经验公式是:pagesize=(寻道时间+旋转延迟)* 传输带宽。对于SAS硬盘而言,通常是1-2M左右;对于flash存储器而言,大概是几十K左右。这个结论估计令很多DBA都很吃惊,因为大部分用BerkeleyDB的人依然在用4K的页面,而MySQL的MyISAM的key buffer竟然是按1K组织的。所以欢迎把你的分析或实验结果发上来一起讨论下,也许我这个结论是错的。

最大的错误在于,也许根本就不该用btree。还是拿网游做例子。一款网游,如果能做到50万的均值在线,那么肯定可以列入行业前十了。假设角色数有1亿左右,一共分为几十组,单组服务器有200万角色,且每个keypage大小为4K,且只能存300个key,并且很糟,全是半满,那么大约需要1万3千个keypage,不过50M内存罢了。每个服务器的表的数量在10-100个左右,那么缓存全部索引页只需要2-3G内存左右。问题就是,既然现在内存这么便宜,为什么不这么做?可是,假如索引全部都在内存中,我为什么还要用Btree ?? 事实上,为了提高索引利用率,网游通常会做分库。于是ACU/角色总数的比例是可以控制在非常高的ratio。

在W公司的时候,我常常给周围的人炫耀我们的cache命中率有多高。我操,高达99.999%。可是今天看到一篇很奇特的文章,“Why a 99%+ Database Buffer Cache Hit Ratio is Not OK”。没读懂,有空继续钻研。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥