0

This question is about creating a new single file database format. I am new to this!

I wonder how SQLite does this- for databases larger than the available memory, SQLite must be reading from certain parts of the file somehow, i.e. reading at position n?

Is this possible at sub-linear runtime complexity? I assume that when SQLite fetches a particular row, it uses a O(logn) index lookup first- so it doesn't fetch the entire index- and then it fetches the row from a particular location in the file. All of this involves not reading the whole file into memory- but FS methods appear not to provide this functionality.

Is fs.skip(n) [pseudocode] done in O(n) or does the OS skip straight to position n? Theoretically this should be possible because in the OS files are divided into blocks- and inodes reference 1-3 levels of array-like structures that locate the blocks, so fetching a particular block in a file should be possible in sub-linear time- without reading in the entire file.

Lucien
  • 776
  • 3
  • 12
  • 40

1 Answers1

-3

I wonder how SQLite does this- for databases larger than the available memory, SQLite must be reading from certain parts of the file somehow, i.e. reading at position n?

Yes. Almost every programming language has documentation that explains how to position the read on a file.

All of this involves not reading the whole file into memory- but FS methods appear not to provide this functionality.

Every file system access API that I know of does support this, and it is explained in the documentation. Examples range from memory-mapped files in Windows (which are "quite" advanced and not supported if you plan to go OS-agnostic), down to something simple like the fseek() method in C that positions a file stream.

I suggest brushing up on your knowledge of file-system access methods in your programming language of choice.

Cody Gray - on strike
  • 239,200
  • 50
  • 490
  • 574
TomTom
  • 61,059
  • 10
  • 88
  • 148
  • Here's one programming language documentation that doesn't let you position the read on a file: https://nodejs.org/api/fs.html#fs_read_file – Lucien Jul 05 '20 at 04:40
  • No, that one is a demonstration of you not reading the documentation. May I bluntly point you to fs.read that has a position parameter allowing you to specify where in the file you start reading. – TomTom Jul 05 '20 at 05:08