python - 优化大量数据的搜索和插入操作

Question

我正在开发一个需要处理大量数据的程序，但我想先将该数据保存在本地存储结构中，然后再将其迁移到数据库。所以，我的问题是:保存该数据的最佳文件类型(或本地存储结构)是什么(这是结构化的，为此目的，我们假设它只是一个 id 和一个名称)，以这样的方式可以优化搜索和插入吗？

我的虽然是一个 CSV 文件，因为数据是结构化的，这可以保存相对大量的数据(在这种情况下，我需要大约 1000 到 100 000 行)，但我不确定是否有还有更好的吗？我的想法是按名称字母顺序对数据进行排序，因此在最坏的情况下，搜索操作将花费 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))

Answer 1

重新实现数据库的想法有利于学习，但对于生产代码来说很可能非常糟糕。

数据库(尤其是关系数据库)通过大量优化取得了长足的进步，而且要接近它真的很难。

话虽如此，一些可能有帮助的注释:

• 如果可能，在内存中处理数据，然后写回磁盘。您将遭受所有 IO 的影响，但至少您不会在磁盘上进行查找。如前所述，pandas 是一个很好的起点
• 对于现代数据库而言，100k 是一个很小的数字
• 读取效率来自于对数据进行排序和索引(现代方法中的 btree+)，这使得搜索 O(logN) 而不是 O(N)。但问题是，在低级中使用 IO 非常困难，特别是如果您使用 CSV，“单个元素”对您来说是由换行符定义的，因此您需要自己实现高级查找
• 就大多数操作系统处理 IO 的方式而言，您无法“插入”数据，因为接口(interface)是顺序的。为了避免插入时的复杂度为 O(N)，请利用老技巧 — 在末尾写入新数据O(N)，并将旧元素标记为以某种方式删除。技巧是能够为标记写入相同数量的字节，即每行都有 bool 标志，并实现“智能”读取逻辑。

<小时/>

关于插入技巧，这是一个简单的例子。假设您有按 id 排序的表，并且数据类似于

id  name    amount
1   Alice   10
2   Bob     20
3   Charlie 30

您需要更新 id = 2 的名称/金额。搜索是 O(logN) (如果您已经实现了正确的 .seek，实际更新会发生什么？如果您写入完全相同的字节数，您可以编写over – 寻找正确的位置并写入。即将 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   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 中通常所说的“真空”。为此，您最好跟踪“重写了多少行”与“总共有多少行”——该比率高于某个阈值是清理的标志。