我正在开发一个程序，该程序需要处理大量数据，但是我想先将该数据保存在本地存储结构中，然后再将其迁移到数据库中。因此，我的问题是：保存数据（结构化的文件和（或本地存储结构）的最佳文件类型是什么，为此，我们假设它只是一个ID和一个名称），以这种方式可以优化搜索和插入？
考虑到数据是结构化的，我虽然是CSV文件，但可以保存相对大量的数据（在这种情况下，我需要大约1000到100000行），但是我不确定是否还有更好的方法在那里。我的想法是按名称的字母顺序对数据进行排序，因此在最坏的情况下，搜索操作将采用O（n）。至于插入操作，由于我无法在两行之间插入一行，因此我正在努力寻找一个很好的解决方案，以便按字母顺序直接在文件中插入行，因此我必须在插入后覆盖整个行我想要的那个（我还考虑过将整个文件读入列表，然后再次写入，但是如果文件太大，则不是最佳实现）。
因此，谁能给我一些关于使用最佳文件类型的想法，哪种方法最适合插入和搜索优化？非常感谢！
（这是我的插入算法，但是会产生随机行为）
def writingOpt(firstName, lastName, birthdate, country):
try:
file = open("players.csv", "r+", newline='')
except FileNotFoundError:
print("File players.csv not found")
else:
with file:
reader = csv.reader(file)
writer = csv.writer(file)
name = firstName + ' ' + lastName
inserted = False
previousRow = []
previousPosition = 0
for row in reader:
if name < row[0]:
file.seek(previousPosition)
if not inserted:
previousRow = [name, birthdate, country]
inserted = True
writer.writerow(previousRow)
previousRow = row
previousPosition += len(','.join(row))
最佳答案
重新实现数据库的想法对学习有好处，但对生产代码却极有可能是坏的。
数据库（尤其是关系数据库）在经过大量优化之后走了很长一段路，要实现这一目标真的很难。
话虽如此，一些说明可能会有所帮助：
如果可能，请在内存中处理数据，然后写回磁盘。您将遭受所有的IO，但至少您没有在磁盘上进行查找。如前所述，pandas是一个很好的起点
就现代数据库而言，100k很小
读取的效率来自对数据进行排序和索引（现代方法中为btree +），这使得搜索为O(logN)而不是O(N)。但是，问题是，很难在底层使用IO，尤其是在使用CSV的情况下，“单元素”是由换行符定义的，因此您需要自己实现高层查找
您不能就大多数操作系统对待IO的方式“插入”数据，因为接口是顺序的。为了避免在插入时出现O(N)，请利用旧的技巧—在O(N)的末尾写入新数据，并以某种方式将旧元素标记为已删除。诀窍是能够为标记写入相同数量的字节，即每行具有布尔标志，并实现“智能”逻辑以进行读取。
关于插入技巧，这是一个简单的示例。假设您有按id排序的表，并且数据类似于
id name amount
1 Alice 10
2 Bob 20
3 Charlie 30
并且您需要更新
id = 2的名称/金额。搜索为O(logN)（如果已实现正确的.seek，则实际更新会发生什么？如果写入的字节数完全相同，则可以覆盖–寻找适当的位置并写入。即更改20到25完全没有问题，您只写所需的内容（不保证，但我们跳过底层细节）。问题是当您需要将
20更改为120时出现的。在大多数情况下，您的存储抽象是顺序的字节流，想象为id,name,amount\n1,Alice,10\n2,Bob,20\n3,Charlie,30\n # old
id,name,amount\n1,Alice,10\n2,Bob,120\n3,Charlie,30\n # new
^ everything beyond this point
needs to be re-written
因此，您平均将得到
O(N/2)（很显然，它与O(N)相同）您可以做的是：在记录现在有效的情况下显示一个“标志”：
valid id name amount
Y 1 Alice 10
Y 2 Bob 20
Y 3 Charlie 30
当需要更新时，通过将相同字节数的标志标记为“ valid”标志将旧行标记为“ invalid”，并在末尾写入新行：
valid id name amount
Y 1 Alice 10
N 2 Bob 20
Y 3 Charlie 30
Y 2 Bob 120
操作是
O(logN)查找行（与以前相同），O(1)覆盖新标志，并O(M)写入新数据（寻找到文件末尾本身不是自由的，但这是另一回事了） 。缺点–现在您需要：使用后备实现乐观搜索-如果您通过树或二进制搜索来寻找数据，则需要检查标志状态，并且如果数据已过时-寻求文件末尾并反向读取
随着更新的到来，未优化的“尾巴”不断增长，越来越将您推向
O(N)复杂性（btree可以提供帮助，顺便说一句）。因此，您最终需要将数据压缩回最佳状态–重新读取所有数据，删除过时的行，对数据进行重新排序，然后再写回磁盘。这是RDBMS中通常称为“真空”的东西。为此，您最好跟踪“重写了多少行”与“总共有多少行”之间的联系–使该比率超过某个阈值是抽空的迹象。