Background:

For very important data, data redundancy needs to be performed during system deployment. That is, multiple copies of these data should be saved. Usually, we store each data backup on multiple nodes for storage using a distributed system.
One of my previous projects was a website system called CatSneeze for finding and selling online movies, which used this architecture:

Among them, a load balancer in google cloud is roled by a Apache server, and I use a round-robin fashion for polling. Requests sent from the front end are forwarded to two machines loaded on AWS EC2 in turn. By this method, the burden of access is reduced and the sustainable number of service users is increased.
MySQLs on two AWSs is deployed in a Master-Slave mode, in which the Master can perform all write operations and partial read operations while the Slave performs partial read operations. Data redundancy is performed on instances2 and instance3. Among them, data replication from master to slave can keep the two databases synchronized at any time.

Definition and Characteristics

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

which is:

1
2
3
4

1. HashMap class is based on Map interface.
2. The keys or values in it are all allowed to be null.
3. It is unsynchronized.
4. No guarantees for entry order and it's consistency.

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering (Default), or by a Comparator provided at queue construction time, depending on which constructor is used. If multiple elements are tied for least value, the head is one of those elements – ties are broken arbitrarily.
The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

Fields

1
2
3
4
5
6
7
8
9
10

//initialize default capacity 
private static final int DEFAULT_INITIAL_CAPACITY = 11;  
//heap
private transient Object[] queue;  
//current capacity  
private int size = 0;  
//comparator
private final Comparator<? super E> comparator;  
//modify times
private transient int modCount = 0;

Functions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//add
public boolean add(E e)   
//get the peek element(not delete)
public E peek()  
//poll the top element(delete)  
public E poll()  
//delete
public boolean remove(Object o)  
//if contains certain element
public boolean contains(Object o)  
//clear 
public void clear()  
//grow capacity
private void grow(int minCapacity)  
//index of
private int indexOf(Object o)

Constructors

1
2
3
4
5
6
7
8
9
10
11
12

PriorityQueue()
Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
PriorityQueue(Collection<? extends E> c)
Creates a PriorityQueue containing the elements in the specified collection.
PriorityQueue(int initialCapacity)
Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
PriorityQueue(PriorityQueue<? extends E> c)
Creates a PriorityQueue containing the elements in the specified priority queue.
PriorityQueue(SortedSet<? extends E> c)
Creates a PriorityQueue containing the elements in the specified sorted set.

TreeMap is a Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.

BACKGROUND

The B+ tree is a kind of Balanced tree which is used to manipulate indexes saving in the relational database system. By using B+ tree, it is faster to retrieve targetted record in the heap file.
In this essay, let me introduce the recent implementation of printing B+ tree in one of my current project.

As usual, B+ has a low level and multiple fanout number, and its non-leaf has a different structure from leaf node. In database lower layer, non-leaf contains multiple keys to search for different leaves. And leaf node contains real key value and RID of record (can be used to get record from heap file).

Analyse

In normal situation, B+ tree has a printing structure as below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

{
"keys":["P"],
"children":[
    {"keys":["C","G","M"],
     "children": [
        {"keys": ["A:[(1,1),(1,2)]","B:[(2,1),(2,2)]"]},
        {"keys": ["D:[(3,1),(3,2)]","E:[(4,1)]","F:[(5,1)]"]},
        {"keys": ["J:[(5,1),(5,2)]","K:[(6,1),(6,2)]","L:[(7,1)]"]},
        {"keys": ["N:[(8,1)]","O:[(9,1)]"]}
    ]},
    {"keys":["T","X"],
     "children": [
        {"keys": ["Q:[(10,1)]","R:[(11,1)]","S:[(12,1)]"]},
        {"keys": ["U:[(13,1)]","V:[(14,1)]"]},
        {"keys": ["Y:[(15,1)]","Z:[(16,1)]"]}
    ]}
]
}

Its tree-formatted structure is like below

We could see from what we mentioned, the non-leaf of B+ tree has “keys” and “children”, but the leaf only has “keys”.
So the printing of leaf and non-leaf is different, we could use different situation in our BFS Algorithm.
Further, The end of each printing component doesn’t have ‘,’. About this problem, we print the first one in the beginning, then print “,” + left one iteratively.

In a corner case, only one leaf node and each entry has same key value, i. e. if leaf entries contain duplicate values, there’s no duplicate key printing anymore, and the RID of it should be in the same quotation marks of former one’s. I designed a way to avoid this problem : remember the former keys when handling leaves, and forget them in the suitable time.