I am reading the book 'SQL performance explained' and when talking about indeces, it says that databases use doubly linked lists to connect index leaf nodes. Each node is stored in a database block and consists of different index entries.
It then says that the index order is maintained at two levels: one within each leaf node, and also within the different leaf nodes themselves (via the linked list), as you can see in the left side of the picture below.
My question is: I understand the advantages of using a doubly linked list for the blocks so that when inserting new blocks it's easier to maintain the order (it's a matter of moving around some pointers). However, within the block itself, if the order is maintained, how is that performant? Assuming than in a block there are a lot of entries, if one were to insert a new entry in the block, wouldn't that be really unperformant (because there is no data structure such as a doubly linked list).