Struktur data untuk alokasi memori dinamis

Pikirkan model pemeriksaan sel. Apakah ada struktur data yang dapat mengalokasikan potongan memori yang berdekatan dengan panjang berapa pun (seperti misalnya malloc di C), dan membebaskannya, sambil menghindari segmentasi memori, dan mengeksekusi setiap operasi dalam kasus deterministik O (log n) terburuk saat n ukuran total memori?

Dengan menghindari segmentasi memori yang saya maksud bahwa jika jumlah total sel bebas adalah F, maka saya harus dapat mengalokasikan segmen yang berdekatan dari sel F atau sekitar sel F.

Bahkan tanpa batas waktu, tidak mungkin untuk "menghindari segmentasi memori" kecuali Anda dapat memindahkan objek yang dialokasikan, seperti dalam pemulung sampah. Lihat Robson's "Batas untuk Beberapa Fungsi Mengenai Alokasi Penyimpanan Dinamis", yang menunjukkan bahwa mengalokasikan byte dalam blok ukuran antara n dan N membutuhkan Ω ( m log ( N / n ) ) byte memori.$m$$n$$N$$\Omega(m \log (N/n))$

Selain itu, sistem buddy mencapai batas ini dan dapat dilakukan dalam waktu logaritmik.

Makalah ini, http://dl.acm.org/citation.cfm?id=3070693 , tepatnya membahas pertanyaan alokasi memori di mana Anda dapat memindahkan barang tetapi dengan biaya.