Editing B-tree (section)

===Insertions and deletions===
If the [[database]] does not change, then compiling the index is simple to do, and the index need never be changed. If there are changes, managing the database and its index require additional computation.

Deleting records from a database is relatively easy. The index can stay the same, and the record can just be marked as deleted. The database remains in sorted order. If there are a large number of [[lazy deletion]]s, then searching and storage become less efficient.<ref>
Jan Jannink.
"Implementing Deletion in B+-Trees".
Section [https://www.alexdelis.eu/M149/B+deletion.pdf "4 Lazy Deletion"].
</ref>

Insertions can be very slow in a sorted sequential file because room for the inserted record must be made. Inserting a record before the first record requires shifting all of the records down one. Such an operation is just too expensive to be practical. One solution is to leave some spaces. Instead of densely packing all the records in a block, the block can have some free space to allow for subsequent insertions. Those spaces would be marked as if they were "deleted" records.

Both insertions and deletions are fast as long as space is available on a block. If an insertion won't fit on the block, then some free space on some nearby block must be found and the auxiliary indices adjusted. The best case is that enough space is available nearby so that the amount of block reorganization can be minimized. Alternatively, some out-of-sequence disk blocks may be used.<ref name="kleppmann_2017" />