python实现简易数据库之⼀——存储和索引建⽴
最近没事做了⼀个数据库project，要求实现⼀个简单的数据库，能满⾜⼏个特定的查询，这⾥主要介绍⼀下我们的实现过程，代码放在过ithub，可参看。都说python的运⾏速度很慢，但因为时间⽐较急，⼯作量⼤，我们还是选择了⾼效实现的python。
⼀、基本要求
1、设计存储⽅式
测试的数据量⼤⼩为1.5GB，最⼤的表有6,001,215条记录。最⼤限度减少I/O次数，减少磁盘占有空间。
2、实现和优化group by，order by
对⼤表进⾏group by 聚集、排序，提⾼查询效率
3、实现和优化TOP k
⾼效率实现TOP k
4、对插⼊不作要求
⼆、总体设计
由于要求主要是对查询做优化，对插⼊删除不作考虑，完全可以采⽤列式数据库，发挥列式数据库的优势。
以下是主要框架（忽略了建表和插⼊数据的过程），图中蓝⾊箭头表⽰⽣成流，橘黄⾊箭头表⽰执⾏流。
整个过程其实是⾄上⽽下建⽴索引，从下往上执⾏查询，具体细节在详细设计中讲述。
三、详细设计
  为了实现⾼效查询，我将表的各个列从表中抽取出来，单独存放，在查询时，只读取所需要的列，不需要读取原始记录，可以⼤⼤的减少I/O次数，但对于select * 这样的查询语句需要读取其他属性，因此我采⽤⾏式和列式结合的⽅式。
1、创建表，⽣成元数据
　在插⼊记录之前需要建表，确定表的格式和完整性约束，如执⾏⼀下建表操作：
create table NATION (N_NATIONKEY int primary key,N_NAME varchar(25),
          N_REGIONKEY int,N_COMMENT varchar(152),
          foreign key (N_REGIONKEY) references REGION(R_REGIONKEY));
将⽣成⼀个meta.table的元数据⽂件，该元数据⽂件第⼀⾏保存的是数据库的所有表名，以下的每⼀⾏为⼀个表的详细描述，格式如下：
[表名1]|...|[表名n]
[表名1]|[表1主键]|[表1第⼀个属性，约束]|[表1第⼆个属性，约束]|...|[[表1第N个属性，约束]]
.
.
.
  测试数据共有8个表，REGION，NATION，LINEITEM，ORDERS，CUSTOMER，PARTSUPP，PART，SUPPLIER。⽰例如下（省略了⼀些表的描述）： 
#meta.table:
REGION|NATION|LINEITEM|ORDERS|CUSTOMER|PARTSUPP|PART|SUPPLIER|
NATION|N_NATIONKEY |N_NATIONKEY INT|N_NAME VARCHAR(25)| N_REGIONKEY INT|N_COMMENT VARCHAR(152)
REGION|R_REGIONKEY |R_REGIONKEY INT|R_NAME VARCHAR(25)|R_COMMENT VARCHAR(152)
.
.
.
  建⽴元数据的作⽤，是在查询处理时可以知道某个表的某个属性在原记录⽂件中的列号，以及该属性属于什么类型，要知道对属性排序和⽐较时必须知道属性类型。因此原数据表meta.table的属性必须按原记录的顺序保存。该数据表常驻内存，以python的有序字典（map）在内存中存放：
{'NATION': OrderedDict([('N_NATIONKEY', 'INT'), ('N_NAME', 'VARCHAR(25)'), ('N_REGIONKEY', 'INT'), ('N_COMMENT', 'VARCHAR(152)'), ('primary', ['N_NATIONKEY'])]), 'REGION': OrderedDict([('R
_REGIONKEY', 'INT'), ('R_NAME', 'VARCHAR(25)'), ('R_COMMENT', 'VARCHAR(152)'), ('primary', ['R_REGIONKEY'])]),...
}
2、插⼊记录
  元数据建⽴好后，可以进⾏插⼊数据，由于时间有限，插⼊数据时我没有进⾏完整性检查，假设插⼊的记录都是合法的，整个插⼊过程完成后，数据记录如下(REGION表)：
#REGION
0|AFRICA|lar deposits. blithely final packages cajole. regular waters are final requests. regular accounts are according to |
1|AMERICA|hs use ironic, even requests. s|
2|ASIA|ges. thinly even pinto beans ca|
3|EUROPE|ly final courts cajole furiously final excuse|
4|MIDDLE EAST|uickly special accounts cajole carefully blithely close requests. carefully final asymptotes haggle furiousl|
  属性之间⽤‘|’分割，在抽取属性列之前，记录⽂件不能压缩，我们将在⽣成列索引时压缩这个原始记录。
3、抽取属性列（同时建⽴记录⾏号与⾏地址的对应表）
  将表中的每个属性单独抽取出来，格式为：
[属性值0]|[⾏号0]
[属性值1]|[⾏号1]
[属性值2]|[⾏号2]
.
.
.
  抽取的列⽰例如下：
#REGION_R_NAME　
AFRICA|0
AMERICA|1
ASIA|2
EUROPE|3
MIDDLE EAST|4
  上⾯的⽰例是REGION表中的R_NAME属性的列，后来发现⾏号可以不⽤保存，读取到数组中后，数组下标就是⾏号，这样可以节省⼀些空间，不过，这个属性列是按原始记录的顺序存放，不能实现按块读取，当记录数很多时，不能放⼊内存，因此这个属性列⽂件在下⼀步之后可以删掉。
  抽取列的同时还要完成两个⼯作，第⼀个是压缩原始记录表，压缩后原始记录不再需要，读记录只需要读压缩记录即可；第⼆个就是建⽴⾏号到压缩后的⾏⾸地址的对应表，这样以后的操作都是按⾏号进
⾏。在扫描原记录⽂件的每⾏时，写压缩⽂件保存压缩记录表，并记录压缩后的每⼀⾏的⾸地址（获得压缩后的地址在）。⾏号与⾏⾸地址的对应表格式如下：
[第0⾏⾸地址]
[第1⾏⾸地址]
[第2⾏⾸地址]
  ⾏号与⾏⾸地址的对应表⽰例如下：　
#REGION
127
171
212
269
  ⽤⾏号代替⾏地址有，可以节省空间，单个表⽂件只要⼤于3*2^32B=12GB（乘以3是因为压缩⽐率约为3:1），字节地址就超过就超过long int能表⽰的范围，⽽⾏号可以表⽰更⼤的表；另⼀个好处，如果后续需要建⽴位图索引，⽤⾏号⽐⾏地址好，因为⾏号是连续的整数，⽽⾏地址是离散在整数空间中，如上⾯的⽰例⾏地址从0直接跳到了127，中间的⼀串整数都没有⽤到，那建⽴的位图索引将是相当稀疏的。  ⾏⾸地址在查询中不会⽤到，只有在最后读取原始记录时才需要转换为⾏号，因此可以将它进⾏压缩，我们⽤gzib压缩，gzib为我们提供⼀个透明的⽂件压缩，所谓透明，就是像读写普通⽂件⼀样，gzib⾃动在缓冲区进⾏压缩和解压。
  python写压缩⽂件主要代码如下：
import gzip
condenseFile= gzip.open(os.path.join(path,fileName+".gz"),'wb',compresslevel = 4)#以⼆进制写，压缩等级为4，值越⼤压缩率越⾼，但时间越长
block = '...'
condenseFile.write(block)
condenseFile.flush()
condenseFile.close()
  读压缩⽂件：
path = os.path.join(DATABASE,"line2loc")
with gzip.open(os.path.join(path,fileName),'rb') as transFile:
locations = ad().split("\n")#也可以只读以⾏ adline()
transFile.close()
4、属性列压缩并建⽴分块索引
  上⼀步我们得到的属性列只是简单从表中抽取出来，这样的属性列有很多冗余，⽐如⼀个表有10000⾏，某个属性只有10个取值，那在属性列中就需要保存保存10000⾏，我们可以按属性值进⾏分组，记录出现该属性值得⾏号，格式如下：
[属性值0]|[出现该值的⾏0]|[出现该值的⾏1]|...|[出现该值的⾏n]
[属性值1]|[出现该值的⾏0]|[出现该值的⾏1]|...|[出现该值的⾏n]
.
.
.
  接下来按属性值排序，这样得到的属性列就有序了，排序的过程中需要⽤到外部排序。排序后的结果，⽰例如下：
#PARTSUPP_PS_SUPPLYCOST
1.0|81868|307973|409984|490169|620444|632371
1.01|25328|36386|172687|243808|287934|558840|774633|775920
1.02|108457|137974|175055|206681|246824|297497|374608
1.03|38563|117772|175895|289935|381497|486960|630290|644984|723651|726647
1.04|284511|314284|327411|392035|639283|721325|754065|783577
.
.
.
6.5|193020|436686|746401
6.51|46883|59908|129012|189045|398695|437094|455012|458310|490801|598787
6.52|54123|129198|145810|223578|336148|377020|377755|379426|430717|442844|500296|549401
6.53|32341|54384|149844|208256|437181|528380
6.54|7164|41427|377948|417213|432345|625698|652283|757838
  上⾯的⽰例截取⾃PARTSUPP表的PS_SUPPLYCOST。排序之后，我们就可以对它进⾏分块读取，为了节省空间和减少I/O次数，我们对这个属性表进⾏分块压缩，并在块上建⽴索引，我们把属性表称为⼀级索引，这个在块上的索引称为⼆级索引。实现时，我们以32KB为⼀块，不过实际操作时我们的块⼤于等于32KB，我们依次将各⾏添加到⼀个字符串string中，每添加⼀⾏我们都会检查string的是否⼤于等于32*1024B，如果⼩于32KB，就继续添加⼀⾏；直到⼤于等于32KB，将string写压缩⽂件，同时记录压缩后的⼤⼩，保存该块的⾸地址和块⼤⼩，然后清空string，开始记录下⼀个块。实现的主要代码如下：
1 scwf = open(os.path.join(scddir,fileName),"w")
2 wf = gzip.open(os.path.join(sortdir,fileName+".gz"),'wb',compresslevel = 4)#压缩属性表
3 block = ""
4 newblock = True#新块标志
5for k in li:#li存放的是有序的属性值和⾏号表
6if newblock == True:
7        blockattr = str(k[0])#块⾸属性值
8        newblock = False
9    line = str(k[0])+"|"
10for loc in k[1]:
11        line += loc+"|"
12    block += line+"\n"
13if len(block) > BLOCKSIZE:
14        startloc = endloc
15        wf.write(block)
16        endloc = wf.tell()
17        size = endloc - startloc
18        scwf.write(blockattr+SPLITTAG+str(startloc)+SPLITTAG+str(size)+'\n')#保存块头的属性值，块⾸地址和块⼤⼩
19        block = ""#块清空
20        newblock = True#新块，下次循环记住新块⾸部属性值
  压缩后⽣成⼆级索引，⼆级索引⽰例如下：
1.0|0|32812
6.52|32812|32810
12.03|65622|32800
17.46|98422|32835
22.92|131257|32787
28.39|164044|32771
33.77|196815|32794
39.29|229609|32810
44.7|262419|32843
数据库简单吗  这两级索引的⽰意图如下：
  上⾯的⽰例中，第⼀⾏表⽰该属性值1.0-6.52为⼀块，块内的属性值在[1.0,6.52)之间，块的起始地址为0，块⼤⼩为32812B，⼆级索引也是有序的，因此建⽴⼆级索引后，我们可以在⼆级和⼀级索引上都进⾏折半查，查询速度很快。
  整个测试数据压缩后的⼀级索引列表：
  对原始记录表进⾏压缩后，不能指定抽取属性列建⽴索引，只能同时对⼀个表的所有属性建⽴索引，这在实际应⽤中有很⼤缺陷，因为有⼀些属性根本就不会再查询条件中使⽤，建⽴的索引浪费了磁盘空间，也延长了建⽴索引的时间。虽然设计了压缩原始记录表，但最后我们实现没有压缩原始记录表，⾏到地址的对应表存的是原始记录的⾏⾸部地址。原始记录⽂件不会删除，这样可以指定表和属性建⽴索引。
  到此，⾃顶向下的存储和索引⼀级建⽴好了，下⼀篇将介绍SQL语句解析和查询处理。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。