On Tue, Jul 27, 2010 at 9:14 PM, Joshua Juran <jjuran@xxxxxxxxx> wrote: > Okay, I have an idea. If I understand correctly, the index is a flat > database of records including a pathname and several fixed-length fields. > Since the records are not fixed-length, only sequential search is possible, > even though the records are sorted by pathname. > > Here's the idea: Divide the database into blocks. Each block contains a > block header and the records belonging to a single directory. The block > header contains the length of the block and also the offset to the next > block, in bytes. In addition to a record for each indexed file in a > directory, a directory's block also contains records for subdirectories. The > mode flags in a record indicate the record type. Directory records contain > an offset in bytes to the block for that directory (in place of the SHA-1 > hash). The block list is preceded by a file header, which includes the > offset in bytes of the root block. All offsets are from the beginning of > the file. > > Instead of having to search among every file in the repository, the search > space now includes only the immediate descendants of each directory in the > target file's path. If a directory is modified then it can either be > rewritten in place (if there's sufficient room) or appended to the end of > the file (requiring the old and new sequentially preceding blocks and the > parent directory's block to update their offsets). Yeah, that's pretty much what bup's current format does, minus appending rewritten dirs at the end when files are added. I've thought of that, but sooner or later, the file would need to be rewritten anyway, and then you end up with odd performance characteristics where the file expands in random ways and then shrinks again when you decide it's gotten too big. And if you do try to reuse empty blocks - which should mostly avoid the endless growth problem - you basically just have a database, including fragmentation problems and multi-user concerns and all. That's what made me think that sqlite might be a sensible choice, since it's already a database :) But maybe there's some simpler way. Have fun, Avery -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html