Data pages are stored contiguously when the index is created and when the index is rebuilt. Otherwise, SQL Server will attempt to keep the pages in physical order. That not being possible, logical order is attempted. You can get gaps in a table because of other writes that are happening in the database. SQL Server uses B+ trees for indexes - the leaf (data) level of the index contains the data but is also a doubly linked list that contains pointers to the next and previous pages. This makes it less important that the table be 100% physically contiguous.

How, in future, SQL determine if page, which Storage Engine asks, is already in memory?

To balance CPU and I/O throughput to achieve good performance and maximize hardware utilization, SQL Server includes 2 asynchronous I/O mechanisms - sequential read ahead and random prefetching

When SQL Server has to scan a large table, the storage engine will initiate the read ahead mechanism to ensure that pages are in memory and they are ready to scan before they are needed by the Query Optimizer.

If you are using Enterprise edition, then there is a mechanism called advanced scanning or merry-go-round scanning that will allow multiple tasks to share full table scans. This advance scanning avoids users to compete for buffer space and taxing other resources on the server.

And which algorithm it uses to keep some free space for new pages?

SQL Server (and Sybase as well :-) ) uses LRU (Least Recently Used) algorithm to keep track of pages that are aged in the buffer pool. It increments a counter every time a page is referenced and decrements the counter every time the lazy writer process sweeps the page.

Any worker thread will check the memory status of Buffer Pool to make sure that there are healthy number of Free pages to honor incoming new requests.

Note that : SQL Server will always keep a minimum number of free pages on the free list, so that it can serve incoming requests without any significant delay. The amount of free space is calculated based on Buffer Pool and amount of incoming requests.

IF there are no free buffers or very little left then :

• If Max Memory is reached then
  • the lazy writer process will sweep parts of buffer pool and based on when the page was last accessed - either leave it or flush it to disk and thereby put the page on the FREE list. A dirty page will not be flushed to disk until the corresponding log records have been written to disk.
• If Max Memory is not reached then
  • SQL Server will commit more reserved pages into the buffer pool.

You can use DMV (in 2005 and up) - sys.dm_os_buffer_descriptors to find the pages in the buffer pool.

Also, there are Memory Manager surface area changes in SQL Server 2012.

KB 2663912 :

Starting with SQL Server 2012, Multi-Page allocations and CLR allocations are also included in memory limits that are controlled by max server memory (MB) and min server memory (MB). This change provides a more accurate sizing ability for all memory requirements that go through the SQL Server memory manager. Carefully review your current max server memory (MB) and min server memory (MB) values after you upgrade to SQL Server 2012.

Highly recommend to read :

• Inside the Storage Engine: What’s in the buffer pool? by Paul Randal
• Performance issues from wasted buffer pool memory by Paul Randal
• Sequential Read Ahead
• Reading Pages