回到上一章

问题引入

• 查找给定键值的元组，如：

  Select    * 
  From   Employee
  Where Dept=‘Toy’ and Salary>=50K
  

• Where条件中涉及了多个属性

下一章 查询执行

回到上一章

问题引入

如何快速地获得指定关系的元组并有效地支持查询处理？

下一章 多维索引

本文写作目的

本文源于自己平常上网时遇到的问题，有的网站由于某些原因域名发生了变化，原域名无法访问了。另一种情况是网站域名未发生改变，只是单纯的被墙，那么也可以采用本文的方法暂时性地访问该网站。不过由于是在线代理，可能在这个过程中的访问记录等信息会被记录，因此不建议使用它来进行一些涉及到个人隐私甚至于财产安全的访问行为。闲言少叙，下面开始正题。

寻找在线代理

这个过程挺简单的，在网页上搜索“在线代理 访问网站”，就可以得到相应的结果。在此推荐使用bing搜索，当然如果是google搜索可用肯定首选google，百度我试了一下效果不理想。下面放上使用三个搜索引擎进行搜索的结果对比：



通过以上对比可以看出，使用bing和google搜索引擎能够比较快的找到结果，baidu找起来可能需要点时间。经过bing和baidu的搜索，其中的第一个链接包含同一个代理网站，而它也是今天我采用的在线代理网站 The Big Bridge，其他功能没有尝试，使用它进行简单的代理访问是可以的。

操作过程

打开网站后,点击左下角的代理服务器链接，如下图所示：

然后在下图红框指定的区域写上自己想访问的网站的域名就可以了。

输入的可以是网站的原域名，也可以是现域名，例如我输入的是

1

developer.google.com

然后就会跳转到指定网站的访问页面，如下图

上图中红框处是当前网站的网址,ps:将这个网址和以前自己使用的网址做个比较就知道究竟是网站域名换了还是被墙了:-)

不过稍显不足的是通过在线代理访问时一些javascript脚本文件没有办法正常加载，所以对于一些网站可能无法正常使用。好了，说了这么多，大家可能看得不耐烦了，那就赶紧试试吧。

回到上一章

内容概览

本章主要解决如下问题：

• 如何将SQL数据类型表示成字段? (3.1)
• 如何将元组表示成记录? (3.2)
• 如何在存储块中表示记录或元组的集合? (3.2)
• 如何用块的集合表示和存储关系? (4,5)
• 如果不同的元组可能具有不同的记录大小，或者记录大小不能整除块大小，或两者兼而有之，如何处理记录大小? (3.4)
• 如果因为修改一些宇段而导致记录大小发生改变，那么将会发生什么情况？我们如何在记录所在的块内找到存储空间，特别是当记录增大 时? (3.5)

下面具体介绍

数据元素和字段

基本SQL数据类型表示成记录的字段

• 定长字符串 char(n)
  • n字节的数组。假如这个属性的值是长度小于n的字符串，则用特定符号填充
• 变长字符串 varchar(n)
  • 长度加内容：分配一个n+1字节的数组
  • 空值-终止字符串
    
• 布尔类型：
  • true
    
  • false
    
• Date类型
  • 日期通常表示为符合某种格式的定长字符串，因此我们可以像表示其它定长字符串一样表示日期。
  • 例如．SQL2标准中日期表示为形如YYYY-MM-DD的10字符字符串，即前四个字符是表示年的数字；第五个字符是连字符；第六个和第七个 字符是表示月的数字，如果必要以0打头
  • 时间也可类似地像字符串一样表示。

• 二进制位

  • 二进制位序列(在SQL2中用类型BIT(n)描述的数据)可以按每8位构成一个字节的方式组装起来。
    

• 枚举类型

  • 可以使用整数编码表示一个枚举类型的值
  • 例如，red->0, bule->1, yellow->2 ……

记录

字段->记录

数据库系统使用的每一种记录类型必须有一个模式。模式由数据库存储，包括记录中字段的名称和数据类型，以及在记录内它们的偏移量。需要存取记录的组成部分时将参考模式。

定长记录的构造

• 最简单的情况是记录的所有字段均为定长、则我们可将字段连接成记录
• 例如，关系MovieStar的声明如下：
  • name：一个30字节的字符串。
  • addres s：VARCHAR(255)类型，用256个字节表示
  • Gender：单一字节， ‘Y’或 ‘N’。
  • birthdate：DATE类型。假设用10字节长的SQL2日期表示这个字段。
  • 所以，MovieStar类型的记录占30+256+1+10＝297
    
• 地址的要求
  • 假设对数据的唯一要求是字段从地址为4的倍数的字节处开始
  • 每一条记录在块内从4的倍数的字节处开始，而且
  • 记录中所有的宇段都从与记录起始偏移量为4的倍数的字节处开始；

记录首部

• 通常在记录中需要保存—些信息
  • 记录模式，或更可能是指向DBMS中存储该类记录模式的位置的一个指针
  • 记录长度
  • 快速地找到下一条记录的开始，避免存取记录的模式，引起额外的磁盘I/O时间戳，指明记录最后一次被修改或被读的时间以及其他可能 的信息。

定长记录在块中的位置

• 表示关系元组的记录存储在磁盘块中

• 它有一个可选的块首部，存储如下各种信息：

  • 与一个或多个其他块的链接，这些块构成一个块网络
  • 这个块在这样一个网络中所扮演的角色的信息
  • 这个块的元组属于哪个关系的信息
  • 一个给出每一条记录在块内偏移量的“目录”
  • 一个“块ID”
  • 指明块最后一次修改和／或存取时间的时间戳

例如：假设记录长度为316字节，使用4096字节的块，其中，12个字节用于块首部，剩余4084字节由数据使用。在这个空间中，我们能装入12条给定的316字节格式的记录，余下的292空闲。

小结：

  到目前为止，最简单的情况是块存储一个关系的元组，并且元组的记录有固定格式。在这种情况下，在块首部的后面，我们把尽可能多的记录装入块内，而留下剩余空间不用。

块和记录的地址表示

• 块的物理地址
  • 主机名(如果数据库存储在不只一台机器上)
  • 设备号；
  • 磁盘的柱面号；
  • 柱面内磁道号(如果磁念有不只—‘个盘向)；
  • 磁道内块号；
  • (某些情况下)记录起始在块内的偏移量。
• 记录的物理地址
  • 块的物理地址＋该记录在此块的偏移量表项中的偏移量
• 块或记录的逻辑地址
  • 具有固定长度的一个任一字节串
• 逻辑地址与物理地址的映射
  • 映射表
    

变长数据和记录

所谓变长可以归为以下几类：

• 大小变化的数据项
• 重复字段
• 可变格式记录
• 极大的字段

具有变长字段的记录

对于这类记录，一个简单而有效的模式是将所有定长字段放在变长字段之前。例如：

具有重复字段的记录

某一定长字段重复出现（长度为L）

• 方法1：记录首部存储一个指针，指向该重复字段出现的第一个位置，例如：
  
• 方法2：保持记录定长，而将变长部分放在另一个块上，在记录本身中存储：指向每一个重复字段开始处的指针，和重复次数或重复结束处
  
  注：该方法同样适用于变长字段

可变格式记录

• 记录没有固定的模式
• 标记字段序列
  • 属性或字段名
  • 字段类型
  • 字段长度
  • 字段值
    

不能装入一个块中的记录

• 大值数据类型
  • 视频或音频“片断”
• 跨块记录
  • 一个记录太大，不能装入一个块中
  • 即使记录比块小，为减少存储空间的浪费，也可以实施跨块记录
  • 一个跨块记录由若干记录片断组成
    在跨块记录或记录片断的首部包含一个二进制位，标明是否为一个片断
    几个二进制位，用于标明是否为第一个或最后一个片断
    指向前后片断的指针
    

BLOBS

• 真正大的记录值或字段值
  • GIF或JFEG等格式的图像
  • MPEG等格式的电影
  • 声音、雷达等各种信号
• 二进制大对象BLOBS
  • 存储
    尽可能存储在连续的块上，以有效检索，或分割，存储在不同的磁盘上
  • 检索
    检索整个BLOB，或其中一部分片断，如“最后45分钟的影片内容”

记录的修改

• 插入
• 删除
• 更新

插入

将一条新记录插入到关系中
若关系的记录无序

• 插入到一个有空闲空间的块，或一个新块中
• 若元组必须以某个固定次序有序
  • 首先，找到该记录应放置的块
  • 若当前块中有空闲空间，则将记录插入块中，并根据需要，在块中滑动记录
  • 否则
    查找临近块
    建立溢出块

删除

• 直接删除记录、清理数据块或删除溢出块等是危险的
• 在记录首部设置删除标记，其余部分继续可用

更新

• 更新定长记录
• 更新变长记录
  • 若更新后记录比旧版本长
    记录滑动，或创建溢出块
  • 若更新后记录比旧版本短
    合并空间，删除溢出块

下一章 索引结构

回到上一章

课程内容

• 存储器层次
• 磁盘存储方式

下面具体介绍

三级存储结构

• 高速缓冲存储器 cache
• 主存储器
• 虚拟存储器、磁盘、文件系统
  • 在操作系统或数据库系统控制下，文件以“块”的方式在磁盘与主存间移动
  • 磁盘读、磁盘写
• 第三级存储器
  • 机器手磁带库、自动光盘库

磁盘

磁盘分类有以下两种

• 磁盘组合 (disk assembly)：由一个或多个圆形盘片组成，围绕一根中心主轴旋转。上下表面覆盖了一层薄薄的磁性材料，用于存储二进制信息。
• 磁头组合(head assembly)

盘片结构如下图：

下面简要介绍一下各个部分

• 磁道被划分为扇区
• 扇区是被间隙分割的磁道片断
• 扇区是不可分割的单位
• 间隙约占整个磁道的10%，用于帮助识别扇区的起点
• 块是磁盘与主存间传输数据的逻辑单元，由一个或多个扇区组成
• 同一时刻位于磁头下的各个磁道构成了一个柱面
• 扇区是磁盘的物理单元
• 块是使用磁盘的软件系统所建立的逻辑单元
• 块由一个或多个扇区构成

磁盘控制器的功能

• 控制磁头，将其定位到一个特定的半径
• 选择一个准备读写的盘面，并从位于该盘面的磁头下的磁道选择一个扇区。控制器还负责识别旋转主轴到达定点的时刻，在此定点位置，所寻扇区在磁头下开始移动
• 将从所寻扇区读取的二进制位传送到计算机主存，或将主存数据写入相应扇区

磁盘存储特性

• 磁盘组合的旋转速度
  • 5400RPM （转/分钟）,即每11ms旋转一周
• 每个磁盘的盘片数目
• 每个盘片的磁道数
• 每个磁道的字节数

磁盘访问特性

• 块读写过程
  • 磁头被定位到包含块的磁道所在的柱面
  • 在整个磁盘组合转动时，组成该块的扇区移动到磁头下面
• 磁盘的延迟时间 ( latency)：从发出块读命令的时刻起，到块的内容出现在主存中止，期间所花费的时间 +
  • 处理器和磁盘控制器处理请求所花费的时间。通常是零点几毫秒，可忽略不计
  • 寻道时间，将磁头定位到合适柱面所花费的时间
  • 旋转延迟，磁盘转动到组成该块的第一个扇区到达磁头是所需的时间，约为磁盘旋转一周时间的一半
  • 传输时间，块的扇区以及各扇区之间的间隙旋转通过磁头所需时间

时间 = 寻道时间 + 旋转时间 + 传输时间 + 其他消耗

其中寻道时间在其中占有相当大的比重，通常以毫秒计，随机寻道时间一般10-40ms
平均要旋转半周才能定位到需要的block，所以旋转时间取旋转一周时间的一半，对于3600RPM(即3600转/秒)的磁盘来说，旋转时间约为8.33ms
传输时间=块大小/传输速率
其他时间消耗：

• 从I/O请求发出到CPU处理中间的时间延迟
• 竞争控制器所需要的时间
• 竞争总线、内存等资源需要的时间
  由于上述这些值很小，所以其他时间消耗一般可以看作0。

顺序读取所用时间分析

上述讨论的是随机访问时间，如果在定位好位置后，进行下一个block的读取操作，那么就不需要 寻道时间 和 旋转时间 了，一旦省去了寻道时间，那么I/O代价就会大幅度降低，例如一个1KB的block，随机访问I/O可能需要时间为20ms，而顺序I/O可能只需要1ms。

块的写操作和修改

• 块的写操作时间与读类似，但可能需要额外的校验检测时间
• 块的修改
  • 将块读入主存
  • 对主存副本修改
  • 将块写回磁盘
  • 如果合适，检查写操作是否已被正确执行

I/O代价

• DBMS的各种操作中，磁盘I/O时间占据了主要处理时间
• 优化性能时主要考虑I/O代价

下一章 数据元素和表示

本文从数据库系统相关的概念讲起，对数据库系统的特点、数据库模式以及DBMS的层次结构进行了介绍。

偶然看见一个Python入门教程，虽然只有一张图片，不过内容丰富，涉及到很多的基础知识。想要入门的童鞋不要错过！

前段时间参加了优酷土豆2016实习生招聘的在线笔试环节，由于选择的是Python开发实习生，所以整个试卷全部是Python相关的，光凭这种专一的程度，就足以落360几条街（想当初我投的360 C++实习岗位，结果笔试时冒出来PHP的题，我也是醉了）。闲言少叙，下面一起来看看今年实习的机试环节编程题。

题型概览

整个笔试部分编程环节共有三道编程题，难度相差不大，考察Python编程的基本功和一般的算法和程序设计思维，下面分别介绍这三道题。

第一题 数字加密

大意如下：输入num为四位数，对其按照如下的规则进行加密：
1、每一位分别加5，然后分别将其替换为该数除以10取余后的结果
2、将该数的第1位和第4为互换，第二位和第三位互换
3、最后合起来作为加密后的整数输出

例如： 输入：1000，输出：5556
时间限制：1s 内存限制：16MB

分析：

此题说得有点啰嗦而且拗口，其实操作过程很简单，下面就它说的前两步进行展开和详细说明：

第一步是给每一位都加5，然后除以10取余数，用这个余数替代原来的数，例如原来的某一位上的数是3，那么3+5%10=8，于是用8替换掉原来位上的3，就这么简单。
第二步题上面说1位和4位互换，2位和3位互换，而输入固定只有4位，那说的直白一些就是把这个数的位颠倒过来了，本来是1234的位置，现在变成了4321位置，这块题目说成这样有混淆视听之嫌
最后就更好说了，颠倒完了合成一个数输出就可以了。

代码实现

经过前面的分析，代码设计的逻辑就已经很清晰了。不过考虑到对输入的整数分离位不太方便，这里将它转成字符串再操作，最后再转成了整数。具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#coding:utf-8

def num_jiami(num):
    '''
        输入num为四位数，操作，每一位加5，然后分别替换为该数除以10取余数后的结果，然后1位和4位交换，
        2位和3位交换，再合起来。
    '''
    num_list=list(str(num))
    for i in [0,1,2,3]:
        num_list.append(str((int(num_list[0])+5)%10))
        num_list.pop(0)
    num_list.reverse()
    result=''.join(num_list)
    return int(result)

代码分析

第一行设定编码字符集为utf-8，因为代码中含有中文。对于Python2.x的解释器，由于默认的字符集为ASCII，遇到中文会出现错误，所以要包含。接下来定义了一个函数，输入参数为num。第8行先讲num转为str类型，假如输入1000，现在就变成了字符串”1000”，然后经过list方法后编程了单个字母组成的列表，具体为：[‘1’,’0’,’0’,’0’]，这就完成了按位分割的功能，而且列表操作起来很方便。9到11行对列表中的每个数加5除以10再取余，这里没有pop再insert，而是一直pop列表首部元素，然后再尾部添加，这样操作的结果与前一种效果是一样的，这样操作完成后，对于[‘1’,’0’,’0’,’0’]来说，将会变成[‘6’,’5’,’5’,’5’]。第12行将列表逆置，对于[‘6’,’5’,’5’,’5’]，就会变为[‘5’,’5’,’5’,’6’]。第13行通过str类的join方法将[‘5’,’5’,’5’,’6’]合成字符串”5556”，最后一行转为int类型再输出。
整个过程比较简单，不过为了提高运行效率，上面有两处代码看似拖沓实则有意而为之：for循环处，

1

for i in [0,1,2,3]

比

1

for i in range(4)

要更高效；最后得到result处没有将整个列表元素依次相加，而是采用了join方法，也是由于join操作更有效率。

第二题 求字符串的全排列

输入：一个字符串 输出：该字符串的全排列
如：输入：’abc’ 输出：abc,acb,bac,bca,cab,cba
时间限制：1s 内存限制：16MB

分析

这道题没什么好分析的，是一个很常见的全排列实现，下面给出递归的实现

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#coding:utf-8

def permutation(result,strs,list):
    if len(list)==1:
        result.append(strs+list[0])
    else:
        for temp_str in list:
            temp_list=list[:]
            temp_list.remove(temp_str)
            permutation(result,strs+temp_str,temp_list)


def getshit(data):
    list_input=list(data)
    result=[]
    permutation(result,'',list_input)
    pp=','.join(result)
    print pp

第三题 字符串解密

大意为：给定一个字符串作为输入，将其中的数字用数字前近邻的字母序列进行替换，字母序列重复的次数等于该数字。最后将字符串输出。
例如： 输入：’a2bc3d1’ 输出：’aabcbcbcd’
时间限制：1s 内存限制：16MB

分析

这道题题目和第一题有一点遥相呼应的味道，第一题加密，这一题解密。虽然规则不同，但是字符串操作的方式基本不变。下面给出实现代码。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def com_baiyi_decode(str):
	
    length=len(str)
    #sys.stdout(length)
    i=0
    temp_dir=[]
    result=''
    while i < length:
        if str[i] in ['0','1','2','3','4','5','6','7','8','9']:
		if temp_dir:
			for j in range(int(str[i])):
			    result+=''.join(temp_dir)
			temp_dir=[]
	else:
		temp_dir.append(str[i])
	i+=1
    print result

总结

上面三道题都是与字符串相关的题，涉及到了str的一些基本操作，如str的拆分、合并；当然还有函数定义，基本的控制语句等。总体来说考察的都是很基础的Python编程知识和编程技能。

在网上见到这样一幅图，感觉挺有意思。快看看自己工作的时候适合听什么样的音乐:-)

MySQLdb作为python操作MySQL数据库的模块，使用起来较为方便（主要是其他的模块没试过⊙﹏⊙‖∣），不过安装过程稍有波折，于是在此记录一下整个安装过程，仅供参考。

下载安装文件

俗话说“巧妇难为无米之炊”，要想安装MySQLdb，首先要下载安装文件，下载地址

安装

这个过程挺简单，不用著名的三板斧，因为安装包中自带setup.py 文件，具体只需要以下几步：

1
2
3
4

$ tar zxvf MySQL-python-1.2.3.tar.gz
$ cd MySQL-python-1.2.3
$ python setup.py build
$ python setup.py install

如果整个过程没问题的话，那么就算是安装完成了，然而事实往往不尽如人意，上面过程中可能会出现下面的问题

问题一： 执行build时提示mysql_config找不到

详细错误：EnvironmentError: mysql_config not found
这种情况说明环境变量的设置有问题，解决方案如下：

首先查找mysql_config的位置，使用

1

$ find / -name mysql_config

比如我的在 /usr/local/mysql/bin/mysql_config

然后修改setup_posix.py文件，在26行：

1
2
3

mysql_config.path = “mysql_config” 
修改为：
mysql_config.path = “/usr/local/mysql/bin/mysql_config”

然后重新执行

1

$ python setup.py build

这样就可以顺利build了