A page table is a vital tool in the important task of memory management, a vital task that each computer operating system must be able to undertake. A page table contains the base address of each page in physical memory; in other words, it is a table that tells the computer where each specific chunk of computer data can physically be found inside the memory chips in your computer.

Page tables are used by operating systems that choose to use a paging scheme for memory management. In paging, incoming data that needs to be stored in memory is broken up into smaller chunks that can be stored away in equal-sized slots in memory; when the piece of information is needed again by the computer, the information has all of its chunks pulled out of memory and reassembled. Where each of these chunks are located while in storage is stored on the page table.

In paging, the chunks described above are called pages, and they are of a specific size as defined by your computer hardware. These pages together in one correctly ordered chunk make up what is called logical memory; in other words, logical memory refers to the information before it is broken up into chunks and is still in the proper order. When a piece of logical memory is split up into separate pages, and each page is stored away in the physical memory somewhere (i.e., in the actual memory chips in your computer), an entry is added to the page table for each page.

A very simple page table has two entries: an identifier for the page full of logical memory, and the address of the location of that memory stored away physically. Here's an example: say you have a physical memory eight units big. In comes a chunk of data four pages big that needs to be stored.

logical memory                 page table                           physical memory

  |--------|      logical page no. | physical location         |--------|    |--------|          
  | page 0 |      =================|==================       0 | page 3 |  4 | page 1 |
  |--------|                     0 | 3                         |--------|    |--------|
  | page 1 |                     1 | 4                       1 |        |  5 |        |
  |--------|                     2 | 7                         |--------|    |--------|
  | page 2 |                     3 | 0                       2 |        |  6 |        |
  |--------|                                                   |--------|    |--------|
  | page 3 |                                                 3 | page 0 |  7 | page 2 |
  |--------|                                                   |--------|    |--------|

So, whenever you want to reassemble the piece of logical memory above, you simply look them up in the page table and pull them in order out of physical memory.

There are a lot of ways to structure a page table, depending mostly on the size you wish to allocate to it against the processing work you'll have to do later when calculating how exactly to retrieve memory pieces. One method is to use a hierarchy of page tables, where the page table itself is broken down into sub-tables, and the main page table, for a particular range of logical values, points to a specific sub-table. This saves on search time, but still has the problem of storing the massive amount of information described, because physical locations can get quite lengthy when a machine has a lot of memory (when there are more addresses, each address gets longer).

Another solution is to use a hash table, where each memory location is compressed by a hashing function. Static hashing is very poor here, as the number of values being hashed changes all the time; a much better choice is linear hashing or extendible hashing because they allow for change based on a changing number of values being stored.

Another solution is an inverted page table, which is a static-sized table that has one entry for each physical location at all times, storing a null value if that location is empty. This way, the size of the table and basic operations on the table can be figured into hardware design, making the system faster. However, it occupies a great deal of space and without some assistance from well-designed hardware, lookups can be quite slow.

Page tables are vital for retrieving information stored in your computer's memory. You use page tables countless times each day, a piece of the underlying operating system most people never have to deal with.