在Raymond Hettingers Pycon 2017演讲中,什么是数据库表示

Question

在Raymond Hettinger的谈话中,他展示了数据库索引的表示.显示在它下面

[None, 4, None, 1, None, None, 0, None, 2, None, 3, None, None, None,None]

我认为他后来在演讲中对此进行了解释,但我无法将各个部分组合在一起

虽然我得到它包含表的索引,该数组是什么以及它是如何生成的？它代表什么？具体来说,列表中第一个位置(第二个,如果不是零索引)中的4代表什么？

链接到Pycon视频

Answer 1

在演示文稿的这一部分,时间限制需要一点简洁和挥手,以便我可以进入Python词典中的中心主题.这里有一个更全面的解释.

平面文件

在关系数据库中,数据可以紧凑地存储在平面文件中:

Row Number  Name       Color     City        Fruit
----------  --------   --------  ---------   -------
0           'guido',   'blue',   'austin',   'apple'
1           'sarah',   'orange', 'dallas',   'banana'
2           'barry',   'green',  'tuscon',   'orange'
3           'rachel',  'yellow', 'reno',     'pear'
4           'tim',     'red',    'portland', 'peach'

请注意,没有浪费的空间(记录或字段之间的孔).

此外,保留插入顺序(新记录按到达顺序附加到末尾).

字母索引

为了加速查找,用户可以在表中创建单独的索引.这是一个可以使用O(log n)二分法搜索的字母索引:

Name      Row Number
--------  ----------
'barry'   2
'guido'   0
'rachel'  3
'sarah'   1
'tim'     4

在Python中,该索引表将使用索引列表表示:

[2, 0, 3, 1, 4]

请注意,没有浪费的空间(条目之间的孔).

哈希指数

通过使用散列函数构造索引表可以获得更好的查找性能.这是一个散列索引表,提供O(1)搜索性能:

Hash   Name      Row Number
----   --------  ----------
0      -         -
1      'tim'     4
2      -         -
3      'sarah'   1
4      -         -
5      -         -
6      'guido'   0
7      -         -
8      'barry'   2
9      -         -
10     'rachel'  3
11     -         -
12     -         -
13     -         -
14     -         -
15     -         -

在Python中,该索引表将使用索引列表表示,但具有None未使用的槽的值:

[None, 4, None, 1, None, None, 0, None, 2,
 None, 3, None, None, None, None, None]

这些特定值是通过在每个名称上运行一些散列函数获得的,得到模16的结果(因为索引表中有16个槽),并执行冲突解决.细节并不重要.

重要的是散列索引表允许比字母索引更快的查找,但它的代价是引入一些"漏洞"并在索引表中浪费一点空间.

结论

实际上,Python 3.6字典与使用散列索引表的数据库具有相同的密度/稀疏度选择.它们都密集地存储核心数据(包括键和值).两者都只存储一次密钥.两者都使用稀疏的索引表来快速O(1)查找.并且都保留了插入顺序.

注意事项

这种类比在许多方面都是不完美的.例如,数据库平面文件将数据直接存储在表中,而Python容器只引用字段值.此外,哈希表通常保存在RAM中,而数据库通常使用持久存储.

但是,类比对于空间利用以及如何保留插入顺序是相当准确的.