数据库的哈希设计

Table of Contents

• 1 用哈希的key代替字符串上的索引，提高查询效率。
  • 1.1 什么是hash
  • 1.2 如何在数据库设计中使用hash
  • 1.3 使用计算列
  • 1.4 如何在多表关联中使用哈希
• 2 库表散列
  • 2.1 ORA_HASH 函数
  • 2.2 哈希拆分例1
  • 2.3 哈希拆分例2
  • 2.4 除留余数法
  • 2.5 拆库

1 用哈希的key代替字符串上的索引，提高查询效率。

索引时一种最为常见的提高查询效率的方式，但在长字符串字段上的索引效果较差，如果多个这样的字段上的联合索引则效果更差。例如，

column name data type

name1	varchar(50)
name2	varchar(100)
other column	varchar(32)

如果经常需用name1和name2上查询，比如经常执行

select * from table where name1=? and name2=?

这种情况就需要在这两个字段上加索引，

create index myindex on table1 (name1,name2)

 

索引提高性能，但当数据量巨大时比如上亿，查询性能就会降低的很快，而且索引也占用存储空间，超大数据量也会使索引占用空间膨胀。比如在name1和 name2上建立的联合索引一行就要使用最少150个字符的空间，数据量大了后空间的蚕食可想而知。据一篇文章说“建立索引，系统要占用大约为表的1.2倍的硬盘和内存空间来保存索引”

因此，我们来使用hash key

1.1 什么是hash

简单说，就是给个字符串，通过一种算法，返回一个整数。返回的整数和给出的字符串就相当于有了一种对应关系。哈希算法有很多种，详见这里 http://en.wikipedia.org/wiki/Hash_function#Hash_function_algorithms

SQLSever中提供了checksum()函数来产生hash key.例如：

select checksum('abc','Tom and Jack')
返回：1094199073
在SQLServer2005上测试结果（以下同）

 

用这种哈希函数，你就可以把长字符串列映射到一个哈希值上来，这个值是唯一的，如果改动字符串的内容，哪怕一个字母，新的哈希值也会不同。实际上，你还可以映射非字符串列，因为哈希算法本质上是对任意长度二进制的映射算法，一切数据类型都可以用二进制来表示。

需要注意的是，实际应用中，有可能出现两段不同的二进制分别经过哈希运算，竟然生成同一个哈希key，这种几率不大，这称为hash collision.它的出现原因也不复杂，主要是由于实际应用中的哈希输出一般都有固定的最大长度限制，超过此长度的哈希输出可能会被进行剪断等操作。这样就有可能本来不应该相同的哈希key经过剪断变成相等的了。具体可参看相关资料，这里不详述，但我们需要当心实际中的哈希值不一定唯一这一点。

1.2 如何在数据库设计中使用hash

让我们继续开始的那个表。当数据量爆多时，建立在name1和name2字段上的索引就有性能问题了。那么根据hash原理，我们对这个表增加一列哈希列,然后对这一列增加索引，而不是对name1和name2增加索引，成为这样，

column name data type

name1	varchar(50)
name2	varchar(100)
other column	varchar(32)
hashkey	integer

create index hashkeyindex on table(hashkey)

hashkey的内容是name1和name2的哈希key，可以通过数据库的checksum来实现。

update table set hashkey=checksum(name1,name)

上面这条语句就会给所有的哈希列赋值。当然更好的办法是建立触发器，每次在插入一条新的记录的时候都对哈希列通过checksum(name1,name2)计算而赋值。

这样，本来建立在两个字段上的索引变成了建立在一个字段上的索引，更重要的是hashkey只有几个byte的大小，比起原来name1+name2=150个字符的大小来说，索引的存储量大大降低了。其实，索引本身也需要一定的搜索，而索引本身越小，搜索一定也就越快。以按名称查询为例，有了哈希列后就可以这么查询

select * from table where hashkey=checksum('张三','地方是飞啊飞鹅的')

由于前面我们提到的哈希key的不一定唯一性，即多个输入可能会被运算成同一个输出（即哈希key)，反过来说，一个哈希key有可能对应多条记录，那么上面的这个查询就可能查出不止一条记录，怎么做呢？很简单

select * from table where hashkey=checksum('张三','地方是飞啊飞鹅的') and name1='张三' and name2='地方是飞啊飞鹅的'

where子句中的哈希key的条件已经使查询大大的减少了返回的行数，再通过真实条件过滤，很快就能查到你真正想要的。这种做法有人会觉得不错，但毕竟在数据库中增加了一列，而且还要写个触发器每次往新增列里更新哈希值。有些麻烦。那这里就可以利用计算列来解决这样的问题。

只是，为什么数据库不直接在联合索引中存放哈希值呢？使用者不就更省事了吗？

1.3 使用计算列

什么是计算列？就是通过计算而得来的列，并非真实存在列(但可以使用 PERSISTED关键字把计算列实际存放在表中）。比如第三列是前两列的和，那么第三列就可设计成计算列，每次查询出的第三列的值实际上是通过计算前两列之和而得出的。这种设计可减少额外存储，减小DB size.

在哈希设计中，就可以创建一个哈希计算列，然后对该哈希计算列创建索引，这样它就不需要真正的存放在表里，实现了只是用来提高查询效率的哈希列与业务表完全分离。

对计算列创建索引需要一些条件，比如计算列的表达式必须有确定性、精确、不能用字符串列等，而哈希key都容易满足。

CREATE TABLE mytable(
    name1 varchar(50),
    name2 varchar(150),
    myhashkey AS checksum(name1,name2)
)
Go
CREATE INDEX hashkeyIndex ON mytable(myhashkey)

1.4 如何在多表关联中使用哈希

多表关联中可以使用hash join，是否使用hash join一般是有数据库系统自己决定。也可以自己手工指定，手工指定方式如下

SELECT a.au_id FROM A a JOIN B b
ON a.name = b.name OPTION (HASH JOIN)

2 库表散列

当数据库表大的一定程度的时候，比如大到上亿或几百亿的记录，查询的性能就会骤降，即使正确的使用索引也无济于事。这个时候就需要使用库表散列的方式来进行处理，实质上就是对表进行拆分，然后按照一定的策略对拆分的表进行查询和其它处理。这里我主要讲哈希策略。

哈希策略就是通过哈希计算，直接定位表。例如：用户表，数据量巨大，需要拆分。以用户的id为哈希计算的关键字，比如userid 是32位的字符串. SDDKSL3KDKSLDKE2FKQKSLEJF9ELAPEK. 最简单的哈希策略是用userid左边第一位的字母作为新表明的后缀。这样，就有了 USER_{S表。26个字母}+10个阿拉伯数字，这样就可以把用户表拆分成36个表。如果查询 userid=UDKLSK3DKSLKDE2FKQSKLEJ9FELAPEKC的记录，可以马上定位到USER_U表 上去。这只是举个简单的例子来说明库表散列，实际中往往用用户名来查，比如根据张三，李四来查，这需要数据库迅速定位张三、李四分别在哪张表中。为了使多个用户均匀的分布在不同的表中，需要一个比较好的哈希函数，我们就不自己设计了，就用oracle的ora_{hash函数来举例。}

2.1 ORA_HASH 函数

 

函数的用法：
select orahash('张三',100,0) from dual
 

结果：79

 

含义：oracle的哈希函数计算出'张三'的哈希值，然后把它放进79号桶中。 100意味着最多只能允许有100个桶。0是种子，用来计算哈希值和安排不同的桶。返回值就是分配的桶号。所谓桶，无非就是组，即把不同的哈希值均匀的放进不同的组里。

 

标准描述：orahash(exp,maxbucket,seedvalue)

 

2.2 哈希拆分例1

有了这个现成的函数，hash拆表就比较简单了。如果你想拆成1000个表，那只需要把max_{bucket设置成1000即可。}

首先，要建1000个user表，分别是 user₀₀₀,user₀₀₁,user₀₀₂,user_003….user₉₉₉. 用户插入的时候，先根据用户名计算它要插入那个表。比如用户名是：'王老虎'.

ora_hash('王老虎',1000,0)的结果是159，那么就需要把该条记录插入到 user_159表中。

insert into user159 (name) values ('王老虎') –实际中还有别的字段

查询的时候，要先定位表，比如查找用户名为 '王老虎', id='SDFEW23SDF' 的记录，同理先通过ora_{hash函数计算，得到159},然后就执行：

 

select * from user₁₅₉ where name='王老虎' and id='SDFEW23SDF'

其它数据库没有ora_{hash这样的函数，所以要自己设计或借用其它的散列函数。} 实际上ora_{hash函数可能被oracle的哈希分区}(hash partition)功能使用。而 hash partition就是oracle的一种把大表数据分而治之的方式。即把一个大表划分成好多个分区。所以在oracle数据库设计中，也就不需要把一个达标拆分成多个小表，而是直接把一个大表拆分成多个分区，然后让oracle自动去管理就行了。但如果做分布式数据库，那么很多工作还是需要自己来做。

2.3 哈希拆分例2

还有一种方式是在每次插入数据的时候才进行判断是否新建hash表。比如有一个叫王刚的记录要被插入，伪码如下：

String userHashName = yourHashFun('王刚');
String tableName = "user_"+userHashName;
if (!exists(tableName)){
    create table...
}
insert into ...

这样做，由于需要做表是否已经存在的判断，所以有一定的性能损耗。

2.4 除留余数法

orahash函数好，但属于oracle专有，离开了oracle，有时我们需要设计自己的hash函数。除留余数法简单易用。

H(k)=k mod p  p<=m

如果userid是数字，则可直接对userid进行此法。比如想要拆分10个表，就取p=10. 比如userid=11，11/10余1，那么就把userid=11的记录分配到表 user1。如userid=23，23/10余3，那么把userid=23的记录分配到表 user3. 除留余数法的好处就是1，简单；2，能相对均匀的把数据分配到不同的子表中去(前提是userid本身比较均匀）。

如果userid不是数字，那么就先对userid进行hash计算(你可以使用现成的 hash计算，比如md5，也可以自己设计），得到数字值，然后再对数字值进行除留余数法。是否均匀，也取决于hash计算的结果是否均匀。

它有一个缺点，原来拆了10个表，系统运行一段后需要拆成50个表会不容易实现。

2.5 拆库

除了如前所述的拆表操作，还可以进行拆库操作。就是把一个大表拆分成多个子表放入不同数据库中。例如user表中的数据可以分别放入5个DB中，分别是 DB1,DB2,DB3,DB4,DB5，每个DB中都有一个user表。5个DB中的user记录加起来就是所有user的记录。hash拆库与拆表方式相同。明白了拆表，拆库也就明白了。所不同的是，定位库和定位表方式有差异。库有可能分布在不同的机器上，所以需要多个数据源。

下面以一段示例性代码说明这种情况

public void test(){
    String userid = "123456";
    String hashvalue = hash(userid);
    String db_connection = getConnection(hashvalue);
}
//用户自己可以实现这个函数(这个函数可以做的很复杂，数据源可以做成动态的）
public abstract Connection getConnection(String db_mark);

//比如下面的一个实现
public Connection getConnection(String db_mark){
    String username="admin";
    String password="admin";
    String ip = "localhost";
    String dbname = "db"+db_mark; //拼凑db name. 
    Class.forName(driveString).newInstance();
    conn = DriverManager.getConnection("jdbc:inetdae7:localhost:1433", username, password);
    conn.setCatalog(dbname);
    return conn;
}

不关怎么实现，只要你能想办法找到你要定位的数据库就行。这个过程就是 DB路由。路由策略根据实际业务情况即可以做的很简单，也可以做的功能强大、复杂无比(因为要负载均衡、要读写分离、要便于统计、要个摘要表、要个缓冲表，要这个要那个，元素越来越多，设计就越来越复杂）。

Hash就是把一大堆乱七八糟的东西用一个小小的东西(一段数字）来代表。这种一大一小的对应的关系极大的缩减了运算空间，所以极大的提高了运算效率。这可以看作是种压缩，看做一种以小御大(想象一下你的食指一动，对面的五指山的食指也一动，多么壮观）。hash后的key们，就如同是对一个庞大世界的精简映像。这正好适合于成万上亿的大数据量的处理。而数据库中的这种被代表现象无处不在。

1. id. 每个表都有一个id或类似id的唯一标识。代表某一行数据，缩减运算空间。对id的各种运算要比对整条记录的数据进行运算快的多。
2. 索引。缩减查询运算空间。
3. Hash.可以看做你自己实现的能跨越多表多库德索引，缩减查询运算空间。

   以小御大，运用之妙，存乎一心。

[e-mail]