Disk Backed Map Collection

Approach 1: Using Map interface 

Map in Java stores data in the form of key-value pair. Navigable Map is an extension of Sorted Map. Navigable Map adds functions to navigate for example higherKey method which is used to get the least key strictly greater than the given key. 
Heap means the area of memory where Java objects are stored. Heap in general is located at bottom of address space and move upwards. whenever we create object using new operator or by any another means object is allocated memory from Heap and when object dies or garbage collected, memory goes back to Heap space in Java.

A lock is a thread synchronization mechanism like synchronized blocks. Locks are created using synchronized blocks, so it is not like we can get totally rid of the synchronized keyword.
To apply lock, we would import java.util.concurrent.locks.Lock interface.

Algotihm:

1.	First, we would import Map interface using import java.util.TreeMap and java.util.NavigableMap.
2.	Declare the map using  NavigableMap<String, Integer> nm =  new TreeMap<String, Integer>() where key is of string type and value is of Integer type.
3.	Now, we would define get/put methods
4.	Now, before calling the put method, check for duplicate key using the containskey() method i.e. nm.containsKey(KEY). If map size gets larger than limit (i.e. disk size) then dump data into file. When map size is larger than the heap size then we can't perform operation in the same time else put a lock before calling the put method then store key and value in map using put method, do the operation and release the lock.

if(!nm.contains.Key(KEY))
{
                //To implement lock, first create a lock
            	Lock lock = new ReentrantLock();
                lock.lock();
                // call to put method
        
                nm.put(KEY,VALUE);
                lock.unlock();
            }




5.	Now, to get the value corresponding to the key, we would call get method (i.e – nm.get(KEY).
6.	
For thread safety,  we can put lock while calling the put method and release the lock when we would complete the traversal.

Example:
Let say we have a data in the form of string :
My name is Amit Khandelwal. I do competitive programming.
Now let us put the data in the map.
Nm.put(My,1)
“My” is neither in map nor in file so just add this {My:1}
Now, add “name”
Check for name in the map, using 
Nm.containsKey(name) since name is not present in the map, so this functions would return false. So, add the “”name” as the key in the map.

Nm.put(name,2)
name is neither in map nor in file overflow so spill 50% of data to file.








Approach 2: We can also do this using serialization of binary tree
Serialization is to store tree in a file so that it can be later restored. Structure of the tree is maintained. And Deserialization is reading tree back form file.

import java.util.*;
import java.util.concurrent.locks.Lock;
class Zycus
{
    public String serialize(Tree root,ArrayList<Integer> aa) 
    {
        if(root==null)
        {
            return "";
        }
 StringBuilder sb = new StringBuilder();
LinkedList<Tree> queue = new LinkedList<Tree>();
queue.add(root);
while(!queue.isEmpty())
{
Tree t = queue.poll();
    if(t!=null)
   {
       sb.append(String.valueOf(t.data) + ",");
       queue.add(t.left);
       queue.add(t.right);
   }else
  {
             sb.append("#,");
   }
}
sb.deleteCharAt(sb.length()-1);
return sb.toString();
}
 // Decodes encoded data to tree.
public Tree deSerialize(String data) 
{
    if(data==null || data.length()==0)
        return null;
 
   String[] arr = data.split(",");
   Tree root = new Tree(Integer.parseInt(arr[0]));
   LinkedList<Tree> queue = new LinkedList<Tree>();
   queue.add(root);
 
   int i=1;
   while(!queue.isEmpty())
  {
      Tree t = queue.poll();
 
      if(t==null)
            continue;
 
        if(!arr[i].equals("#")){
            t.left = new Tree(Integer.parseInt(arr[i]));    
            queue.offer(t.left);
 
        }else
       {
            t.left = null;
            queue.offer(null);
        }
        i++;
 
        if(!arr[i].equals("#"))
       {
            t.right = new Tree(Integer.parseInt(arr[i]));    
            queue.offer(t.right);
       }else{
            t.right = null;
            queue.offer(null);
        }
        i++;
    }
 
    return root;
}
}
class Tree{
	int data;
	Tree left,right;
	Tree(int d){
		data=d;
		left=right=null;
	}
}
class SND{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0){
			int n=sc.nextInt();
			Tree root=null;
			if(n==1){
				System.out.println(sc.nextInt());
				n--;
			}
			while(n-->0){
				int n1=sc.nextInt();
				int n2=sc.nextInt();
				char lr=sc.next().charAt(0);
				if(root==null){
					root=new Tree(n1);
					switch(lr){
						case 'L':root.left=new Tree(n2);
						break;
						case 'R':root.right=new Tree(n2);
						break;
					}
				}
				else{
					insert(n1,n2,lr,root);
				}
			}
		ArrayList<Integer> aa=new ArrayList<Integer>();
		GfG g=new GfG();
		String s=g.serialize(root,aa);
		Tree root1=g.deSerialize(s);
		inorder(root1);
		System.out.println();
		}
	}
	public static void inorder(Tree root){
		if(root==null)
			return;
		inorder(root.left);
		System.out.print(root.data+" ");
		inorder(root.right);
	}
public static void insert(int n1,int n2,char lr,Tree root){
	if(root==null){
		return;
	}
	if(root.data==n1){
		switch(lr){
			case 'L':root.left=new Tree(n2);
			break;
			case 'R':root.right=new Tree(n2);
			break;
		}
	}
		insert(n1,n2,lr,root.left);
		insert(n1,n2,lr,root.right);
}
}


We can keep track of nodes in tree using hash table : 
1.	Have the insert function return a reference to the node inside the Tree class, then use some auxiliary hash table to store those references. To do an insertion, we would insert the key and its priority, get handed back a reference to the node in the  heap, then add the key and the reference to an external hash table (using HashMap).
2.	We will use an intrusive data structure by having each key to store in the heap actually be the complete Tree structure. The implementation of the heap would then overwrite the relevant fields of the input to wire it into the heap structure, and provided that we stored the nodes in some reasonable fashion we could just look them up as needed.