Is it possible to efficiently insert or remove bytes from the middle of a large file, and if so how? Or am I stuck rewriting the entire file after the point where the data was inserted or removed?
[A lot of Bytes][Unwanted Bytes][A lot of Bytes] - > [A lot of Bytes][A lot of Bytes]
or
[A lot of Bytes][A lot of Bytes] - > [A lot of Bytes][New Inserted Bytes][A lot of Bytes]
If it is a flat file, you have to rewrite the portion after the edits. If it is a file with logical structure (e.g., pointers to other parts of the file), then updates can be very efficient.
There is no way to insert data or remove data in O(1) in C# nor C++ nor any language with standard APIs or class libraries.
The best you could do is have some kind of file format that you define yourself, it could support O(1) insertions and removal. But you'd have to probably deal with fragmentation.
You could perhaps also look at an SQL database like sqlite which would take care of the complexities for you.
You have to copy the file. At best, you may be able to get away using Sparse Files, but only if the 'A lot of Bytes' is Zeros.
The most efficient way would be to seek to the position where you want to insert the element, read everything up to the end, insert the new element and copy back the rest.
The problem's not a language one, but actually how data is stored in media, where everything's just a long sequence of bits. You can imagine it as a single strip of paper with the data written out in pen. If you want to insert something, you'll have to push back everything that comes afterwards. Of course, if you've got a lots of empty space between blocks of data, you can insert your stuff in there (which is the idea behind Sparse Files), but that's hardly space-efficient.