tag

#external-memory

30 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Funnel Sort

Funnel Sort Funnel sort is a cache oblivious sorting algorithm that achieves optimal cache complexity without knowing cache size or block size. It relies on a recursive multiway merge structure called a funnel . The algorithm matches the lower bound for comparison sorting in the external memory model. Model Assume: $N$ elements block size $B$ cache size $M$ tall cache condition $M = \Omega(B^2)$ The algorithm does not know $M$...
algorithms sorting cache-oblivious external-memory
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Stream Sort by Buffer

Stream Sort by Buffer Stream sort by buffer sorts incoming data in memory-sized batches. It reads a fixed number of elements, sorts that buffer, emits the sorted block, and repeats. You use it when the full input is too large or too delayed to sort all at once. Problem Given a stream of values and a buffer capacity ( B ), produce sorted chunks or sorted runs from the stream....
algorithms sorting streaming buffer external-memory
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

External Replacement Selection

External Replacement Selection External replacement selection is the disk-oriented version of replacement selection. It generates long sorted runs from data that does not fit in memory, forming the first phase of external merge sort. You use it when sorting large datasets stored on disk. Problem Given a dataset too large to fit into memory and a memory buffer of size ( M ), generate sorted runs on disk such that:...
algorithms sorting external-memory replacement-selection
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Cache Oblivious Sorting

Cache Oblivious Sorting Cache oblivious sorting uses recursive structure to obtain efficient memory hierarchy behavior without knowing the cache size $M$ or block size $B$. The algorithm is written as if memory were flat, but its recursive subproblems eventually fit into every cache level. This approach is useful when the same implementation should perform well across different machines and storage hierarchies. Model The cache oblivious model assumes: memory is transferred...
algorithms sorting cache external-memory
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Polyphase Merge Sort

Polyphase Merge Sort Polyphase merge sort is an external sorting algorithm for merging many sorted runs using a limited number of files or tapes. It avoids the rigid redistribution step used by balanced merge sort. Instead, it places different numbers of runs on different input files so each merge phase naturally prepares the next phase. This method was especially important for tape drives, where rewinding and redistribution were expensive. The...
algorithms sorting external-memory merge-sort
Wiki › Algorithms › 02. Data Structures ›

3. Specialized, Persistent, Concurrent, and External Structures

3. Specialized, persistent, concurrent, and external structures section name 3.1 Persistent Data Structures 3.2 Functional Data Structures 3.3 Succinct and Compressed Structures 3.4 Geometric Data Structures 3.5 Concurrent and Lock-Free Structures 3.6 External-Memory and Database Structures 3.7 Probabilistic Data Structures
algorithms data-structures persistent concurrent external-memory
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

External Bucket Sort

External Bucket Sort External bucket sort extends bucket sort to data that does not fit in memory. It partitions records into ordered buckets stored on external storage, sorts each bucket independently, and concatenates the buckets in key order. The method works well when the key distribution is known well enough to create buckets of manageable size. Problem Given a large dataset and a key function, sort all records using bounded...
algorithms sorting external-memory bucket-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Chunked Sort

Chunked Sort Chunked sort divides a large input into smaller chunks, sorts each chunk, and then combines the sorted chunks. It is a practical pattern for sorting data that is too large or too inconvenient to process as one array. The method appears in external sorting, streaming systems, parallel sorting, and batch data pipelines. Problem Given a sequence of $N$ records and a memory limit that can hold only $M$...
algorithms sorting external-memory chunking
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Database External Sort

Database External Sort Database external sort is the disk-based sorting procedure used inside relational database query engines. It appears in query plans for operations such as ORDER BY , GROUP BY , DISTINCT , window functions, and sort-merge joins. The method is usually a variant of external merge sort with database-specific concerns: rows, tuple comparison, memory quotas, spill files, collation rules, NULL ordering, and stable execution under limited working memory....
algorithms sorting external-memory database
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

External Sample Sort

External Sample Sort External sample sort is a distribution-based external sorting algorithm. It selects a sample of the input to determine splitters, partitions the data into balanced buckets using those splitters, and then sorts each bucket independently. The method reduces the number of merge passes by ensuring that buckets are roughly equal in size. Problem Given a large dataset that does not fit in memory, sort it efficiently while minimizing...
algorithms sorting external-memory sample-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

LSM Compaction Sort

LSM Tree Compaction Sort LSM tree compaction sort organizes sorting as a sequence of merges across levels in a Log Structured Merge (LSM) tree. Data is inserted in batches, stored as sorted runs, and periodically merged into larger sorted structures. Sorting emerges as a byproduct of compaction. Each level maintains sorted order, and merges ensure global ordering across levels. Model Assume: data arrives in batches memory buffer of size $M$...
algorithms sorting external-memory lsm-tree
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Memory Mapped External Sort

Memory Mapped External Sort Memory mapped external sort uses memory-mapped files to sort data larger than ordinary working memory. Instead of manually reading and writing file blocks with explicit I/O calls, the program maps file regions into virtual memory and lets the operating system page data in and out. This can simplify implementation, but it does not remove the external-memory problem. The algorithm still needs chunking, sorted runs, and merging...
algorithms sorting external-memory memory-mapped-files
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

External Radix Sort

External Radix Sort External radix sort extends radix sort to datasets larger than memory. It processes keys digit by digit and uses external storage to hold intermediate buckets. Unlike comparison-based external sorts, it exploits the structure of keys to achieve linear-time sorting. This method is effective when keys have fixed length or can be decomposed into digits. Problem Given a large dataset with keys that can be decomposed into digits...
algorithms sorting external-memory radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Sort Merge Join Sort Phase

Sort Merge Join Sort Phase The sort phase of sort-merge join orders each input relation by the join key before the merge phase begins. If an input is already ordered by a suitable index or previous query operator, the database can skip sorting that input. This phase is important because the merge join itself requires ordered streams. Without sorted inputs, the join cannot advance both sides efficiently. Problem Given two...
algorithms sorting external-memory database joins
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Parallel External Merge Sort

Parallel External Merge Sort Parallel external merge sort extends external merge sort by using multiple processors, threads, and storage devices to increase throughput. It parallelizes both run generation and merging while keeping I/O mostly sequential. The algorithm is used in large-scale systems where sorting terabytes of data requires distributing work across CPUs and disks. Problem Given a dataset much larger than memory, sort it efficiently using multiple processors and parallel...
algorithms sorting external-memory parallel
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Replacement Selection

Replacement Selection Replacement selection is a run generation technique used in external sorting. It produces sorted runs that are often longer than the available memory size by using a priority queue. You use it when sorting data that does not fit in memory. Problem Given a stream of elements and limited memory of size ( M ), produce sorted runs on disk such that: each run is sorted runs are...
algorithms sorting external-memory replacement-selection
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Balanced K Way Merge Sort

Balanced K Way Merge Sort Balanced k way merge sort is an external sorting algorithm that repeatedly merges sorted runs in groups of at most $k$. Unlike polyphase merge sort, it tries to keep the merge work evenly distributed across passes. It is a simple and common model for large file sorting. The input is first divided into memory-sized chunks, each chunk is sorted internally, and then the resulting sorted...
algorithms sorting external-memory merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Buffer Tree Sort

Buffer Tree Sort Buffer tree sort uses a buffer tree to sort data in the external-memory model. Instead of sorting all records directly, it inserts records into a high fanout search tree whose internal nodes hold buffers. When a buffer fills, records are pushed downward in batches. The purpose is to reduce random I/O. Records move through the tree in large blocks, which makes the algorithm efficient when data is...
algorithms sorting external-memory buffer-tree
Wiki › Algorithms › 02. Data Structures › 3. Specialized, Persistent, Concurrent, and External Structures ›

3.6 External-Memory and Database Structures

3.6 External-memory and database structures, 35 index slug name 1 external-memory-structure External Memory Structure 2 block-model Block Model 3 buffer-pool Buffer Pool 4 page-cache Page Cache 5 slotted-page Slotted Page 6 heap-file Heap File 7 sorted-file Sorted File 8 clustered-index Clustered Index 9 secondary-index Secondary Index 10 b-tree-index B Tree Index 11 b-plus-tree-index B Plus Tree Index 12 lsm-tree LSM Tree 13 memtable Memtable 14 sstable SSTable 15 bloom-filter-index Bloom...
algorithms data-structures external-memory database
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Spill Sort

Spill Sort Spill sort is a practical external sorting pattern used when an operator begins as an in-memory sort but exceeds its memory budget. When memory fills, the current data is sorted and spilled to temporary storage as a run. After all input has been read, the spilled runs are merged. This is common in databases, query engines, log processors, and stream processors. Problem Given an input stream and a...
algorithms sorting external-memory database
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Cache Aware Sorting

Cache Aware Sorting Cache aware sorting refers to algorithms that are designed with explicit knowledge of the memory hierarchy, especially cache size and cache line (block) size. The goal is to minimize cache misses by structuring memory access patterns carefully. This model is more detailed than the standard RAM model and closer to real hardware behavior. Model Assume a two-level memory model: Fast memory (cache) of size $M$ Slow memory...
algorithms sorting cache external-memory
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Distribution Sweeping Sort

Distribution Sweeping Sort Distribution sweeping sort is an external-memory sorting method based on partitioning. Instead of repeatedly merging sorted runs, it divides the input into key ranges, places each element into the correct range, sorts each range separately, and then concatenates the sorted ranges. The method is useful when range partitioning can be done efficiently and each partition can later be sorted with bounded memory. Problem Given a dataset too...
algorithms sorting external-memory distribution-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Loser Tree Merge

K Way Loser Tree Merge K way loser tree merge is an optimized method for merging multiple sorted runs. It replaces the standard heap with a tournament tree that stores the loser of each comparison. This reduces the number of comparisons and improves performance in external sorting. It is widely used in high-performance external merge sort implementations. Problem Given $k$ sorted input streams, merge them into one sorted output efficiently....
algorithms sorting external-memory merge loser-tree
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

External Merge Sort

External Merge Sort External merge sort is a disk-based sorting algorithm designed for datasets that exceed main memory. It minimizes random I/O and relies on sequential reads and writes, which are efficient on disks and object storage. You use it when the input size is much larger than RAM, for example multi-gigabyte or terabyte scale data. Model Assume: Input size: $N$ elements Memory capacity: $M$ elements Block size: $B$ elements...
algorithms sorting external-memory merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

B Tree Bulk Load Sort

B Tree Bulk Load Sort B tree bulk load sort constructs a B-tree from a dataset by first sorting the data and then building the tree in a single pass. The sorting phase produces ordered records, and the bulk loading phase organizes them into tree nodes efficiently. This method avoids inserting records one by one into a B-tree, which would cause many random I/O operations. Problem Given a large dataset,...
algorithms sorting external-memory b-tree
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Winner Tree Merge

K Way Winner Tree Merge K way winner tree merge is a tournament-tree method for merging multiple sorted streams. Each leaf represents one input stream, and each internal node stores the winner of a comparison between its children. The winner is usually the smallest current element among the competing streams. After the winner is emitted, only the path from that stream's leaf to the root must be recomputed. Problem Given...
algorithms sorting external-memory merge winner-tree
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Tape Merge Sort

Tape Merge Sort Tape merge sort is an external sorting algorithm designed for sequential storage. It was historically used with magnetic tapes, where random access was expensive or unavailable. The algorithm writes sorted runs to multiple tapes, then repeatedly merges runs from input tapes onto output tapes. The same idea still matters for sequential external storage: make long sequential reads and writes, avoid random seeks, and reduce the number of...
algorithms sorting external-memory merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

TPMMS

Two Phase Multiway Merge Sort Two Phase Multiway Merge Sort (TPMMS) is a practical external sorting algorithm used in database systems. It assumes that all sorted runs can be merged in a single pass using available memory buffers. The method minimizes the number of disk passes, which dominates cost in external memory settings. Model Let: $N$ = total number of elements $M$ = memory capacity $B$ = block size Memory...
algorithms sorting external-memory database
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Replacement Selection Run Generation

Replacement Selection Run Generation Replacement selection run generation is the first phase of an external sort. It produces sorted runs from an input stream using a heap. Unlike simple chunk sorting, which creates runs of about memory size, replacement selection often creates runs about twice as large when input order is random. Longer runs reduce the number of later merge passes. Problem Given an input stream too large for memory,...
algorithms sorting external-memory heap
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Cascade Merge Sort

Cascade Merge Sort Cascade merge sort is an external sorting method that organizes merging into a pipeline of stages. Each stage merges a group of sorted runs and passes the resulting larger runs to the next stage. The purpose is to reduce repeated redistribution and make external merging easier to schedule. It is most useful when runs arrive gradually or when storage bandwidth can be used by several merge stages...
algorithms sorting external-memory merge-sort