DNS - Configuring Forward and Reverse Lookup Zones

Things you should know 

Domain Name System (DNS) refers to the domain name resolution mechanism, which allows using domain names, instead of IP addresses to access a domain. E.g. you can use http://facebook.com/ instead of http://66.220.149.11/ to access the facebook website.

The process of converting a DNS name to an IP address is known as DNS name resolution process.

A forward lookup zone is a DNS zone in which hostname to IP address relations are stored. When a computer requests the IP address of a specific hostname, the forward lookup zone is queried and the result is returned.

A reverse lookup zone does just the opposite. When a computer requests the hostname of an IP address, the reverse lookup zone is queried and the result is returned.

Practical Implementation

Open DNS Window and uncheck IPv6

Start - Administrative Tools- DNS

Right Click on Server

Select Properties

Select only the following IP Address

Uncheck IPv6 entry

OK

DNS - Uncheck IPv6

Configuring forward lookup zone

Expand Server Node

Right Click on Forward Lookup Zones

New Zone

DNS - Opening New Zone Wizard

New Zone wizard will appear. Give Next. Now you have to select the zone type.  

What is a zone? What are its types?

A zone is an entity that stores the records (information) about the objects that it manages. A record consists of a domain and its corresponding IP address. There are three types of zones. 

• Primary Zone:  You can add and alter resource records in a primary zone.

• Secondary Zone: It contains read-only records obtained from a primary DNS zone.

• Stub Zone:  Stub zone in Microsoft server 2008 is a specialized version of a secondary zone. A stub zone contains only those resource records that are necessary to identify the authoritative DNS server for that zone. 

As we are creating a new zone for the first time, hence select primary zone.

DNS - Zone Type

Keep the option Store the Zone in Active Directory checked and give next.

Next is Zone replication scope.

Zone Replication Scope	Description
All DNS servers in the Active Directory forest	Replicates zone data to all DNS servers running on domain controllers in the Active Directory forest. Usually, this is the broadest scope of replication.
All DNS servers in the Active Directory domain	Replicates zone data to all DNS servers running on domain controllers in the Active Directory domain. This option is the default setting for Active Directory-integrated DNS zone replication in the Windows Server 2003 family.
All domain controllers in the Active Directory domain	Replicates zone data to all domain controllers in the Active Directory domain. If you want Windows 2000 DNS servers to load an Active Directory zone, this setting must be selected for that zone.

We will keep the default and give next. 

Provide the zone name. e.g. ciots.com

Select - Allow both nonsecure and secure dynamic updates and give next and finish.

An entry will be created for ciots.com in the forward lookup zones.

Select ciots.com, right click on it and select New Host. A host is used to resolve an IP address to a device in a domain. The device can be a computer, printer etc. 

DNS - Adding a new Host

The New Host window will appear.

Now consider for the domain ciots.com we have the FTP server at location 192.168.1.12 for which we have to create the DNS forward lookup entry. 

Enter name ftp and provide the IP address as 192.168.1.12

DNS - Configuring new host

Finally click on Add Host. With this we have completed forward lookup entry.

Video Tutorial Creating a DNS Forward Lookup Zone

Configuring reverse lookup zone


Right click on Reverse Lookup Zones and Select New Zone. The settings will be nearly same as the configuration settings of forward lookup zone.

Select IPv4 Reverse Lookup Zone – Next
Enter Network ID as 192.168.1 – Next
Allow both nonsecure and secure dynamic updates – Next – Finish

Right Click on the node created and select New Pointer (PTR)

DNS - Adding new PTR

Enter host IP address: 192.168.1.12

Host name: browse and select ftp.ciots.com

OK

Now we will use the nslookup command to verify these entries.

Verify Forward Lookup entry

In the command prompt, enter nslookup ftp.ciots.com , this will give the associated IP address.

Verify Reverse Lookup entry

In the command prompt, enter nslookup 192.168.1.12 , this will give the associated host name.

DNS - nslookup command

Video Tutorial Creating a New Reverse Lookup Zone

Creating a user in Active Directory

There are four ways for creating users. Let's see each of them one by one.

Using the GUI


Steps

Start
Administrative Tools
Active Directory Users and Computers
mcitp.com (expand the domain node by clicking on plus)
Right Click on Users
New User
Configure the details and create the new user.

Creating a user in Active Directory (GUI)

Using Command

To create a user Amarjeet with login name amar in the domain mcitp.com and the user must change password after first login.

Open command prompt and execute the following command.

dsadd user "CN=Amarjeet, CN=Users, dc=mcitp, dc=com" -samid amar 
-pwd * -mustchpwd yes

Creating a user in Active Directory (Command)

Now the user can login with the name amar and has to change password at the time of first login.

How to Add a Client Machine in a Domain

Steps

Right Click on My Computers

Properties

Go to Computer Name Tab Click on Change button

Select Domain

Give domain name e.g. mcitp.com

Provide Server Administrator’s credentials 

It will verify and the system will restart.

Now log in on the domain with the Active Directory user credentials.

Click here to know how to create a user in Active Directory.

Installing Active Directory in Windows Server 2008

Before Installing Active Directory we have to configure the machines. Click here to know more

Note : To install Active Directory we need at least 2 machines in workgroup. One will be the server machine and the other will be a client.

What is Active Directory Domain Services (AD DS) ?

Active Directory (AD) is a structure used on computers and servers running the Microsoft Windows operating system (OS). AD is used to store network, domain, and user information and was originally created by Microsoft in 1996. It was first deployed on Microsoft Windows 2000.

Active Directory Domain Services (AD DS) stores directory data (about users, computers, organizational units and other network resources)  and manages communication between users and domains, including user logon processes, authentication, and directory searches. An Active Directory domain controller is a server that is running AD DS.

AD DS provides a distributed directory service that you can use for centralized, secure management of your network.

Installing Active Directory on Windows Server 2008

Start - run - dcpromo - OK

The installation wizard will appear for Active Directory. Read the instructions and give Next twice. 

As we are creating domain for the first time, hence select Create a new domain in a new forest

Installing AD - Creating new domain

Give FQDN i.e. Fully Qualified Domain Name. e.g. mcitp.com

Installing AD - Giving FQDN

Specify Forest Functional Level

If the organization where we are doing this setup is already having some other machines running any version of Windows Server and you want to establish trust relationship with those machines, then select the lowest version from the list.

As this is our first machine and no other servers exist, hence select Windows Server 2008.

Installing AD - Specifying Forest Functional Level

Now when you give next, a warning will appear regarding IP, give yes and continue.

As DNS is not installed yet on the system, a message will appear in this regard. Give yes and continue.

Next it will ask for the path where the database of the Active Directory will be stored on the disk. Keep  the default values and give next.

Give directory service administrator password - e.g. admin@123 and give next.

The installation will start. 

Check Reboot on Completion so that system will restart after completing the AD installation.

Now

Create a user. Click here to know more

Bring the Client Machine in Domain. Click here to know more

and Finally login from client on the domain with the new user name and password.

Installing AD - Login Screen

Preparing Machines Before Installing Active Directory

There are few settings need to be done before we start with Active Directory (AD) installation.

What we have already done


We have created two machines and already installed operating system.

• Server Machine : Windows Server 2008
• Client Machine  : Windows XP

Now we will take these settings further. 

As we are working with Oracle VM Virtual Box Manager, for each machine created,

1. Select the Machine
2. Go to Settings
3. Go to Network Tab
4. Select Attached to - Bridge Adapter

Configuring Bridge Adapter Settings (Click on the image to enlarge)

Configuring Server IP Address

Go to Network and Sharing Center

Manage Network Connections

Right Click on Local Area Connection

Properties

Select Internet Protocol Version 4 (TCP/IPv4)

Click on Properties

Set the following IP Address

Configure Client IP Address

Use the following IP settings for client machine.

Change the Computer names (Both Systems)

Right Click on My Computer

Properties

Change Settings

Change (Button)

Give Computer Name 

OK

and restart the computer.

Turn Off Firewall (Both Systems)

Start

Control Panel

Windows Firewall

Turn Windows Firewall On or Off

Turn Off Windows Firewall

OK

Firewall Settings

Turn on Network Discovery on Server (Optional)

Right Click on My Network Places icon in the Tray
Go to Network and Sharing Center
Click on the Arrow button
Select Turn on network discovery
Apply

Turn on Network Discovery

Ping Systems and assure that they are connected

Start - run - ping 192.168.1.10 –t

Now we can start with active directory installation. Click Here to know more

Building a Binary Tree using Inorder and Postorder Traversals in Java

class TNode
{
 int data;
 TNode left;
 TNode right;

 TNode(int d)
 {
  data = d;
  left= null;
  right=null;
 }
}

class TreeBuilder
{
 static int postIndex;
 static int[] in, post;
 TNode Start;

 static void setValue(int[] i, int[] p)
 {
  in = i;
  post = p;
  postIndex=in.length-1; //Change 1
 }

 static int findInIndex(int inStart, int inEnd, int value)
 {
  for(int i=inStart; i<=inEnd; i++)
   if(in[i]==value)
   return i;

  return -1;
 }

 //Main method with the logic for building tree using Pre and Inorder traversals
 static TNode buildTree(int inStart, int inEnd)
 {
  if(inStart>inEnd)
   return null;

  TNode node = new TNode(post[postIndex--]); //Change 2

  if(inStart==inEnd)
   return node;

  int inIndex = findInIndex(inStart, inEnd, node.data);
  
  //Change 3

  node.right=buildTree(inIndex+1, inEnd);
  node.left=buildTree(inStart, inIndex-1);

  return node;
 }
}

class TreeBuilderDemo 
{
 public static void main(String[] args) 
 {
  int[] in = {8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7};
  int[] post = {8, 10, 11, 9, 4, 5, 2, 6, 7, 3, 1};

  TreeBuilder.setValue(in, post);

  TNode start = TreeBuilder.buildTree(0,in.length-1);

  System.out.print("\nPreorder\t: ");
  printPreorder(start);

  System.out.print("\n\nInorder\t\t: ");
  printInorder(start);

  System.out.print("\n\nPostorder\t: ");
  printPostorder(start);

  System.out.println("");
 }

 static void printInorder(TNode node)
 {
  if (node == null)
   return; 

  printInorder(node.left);   
  System.out.print(node.data + "\t "); 
  printInorder(node.right);   
 }

 static void printPreorder(TNode node)
 {
  if (node == null)
   return; 

  System.out.print(node.data + "\t ");
  printPreorder(node.left);   
  printPreorder(node.right);   
 }

 static void printPostorder(TNode node)
 {
  if (node == null)
   return; 

  printPostorder(node.left);   
  printPostorder(node.right);   
  System.out.print(node.data + "\t ");
 }
}

Click here to learn Building a Binary Tree using Inorder and Preorder Traversals in Java.

Cards Arrangement Program in Java

Aim

Write a program to print the source sequence of cards, for one card below the deck & every alternate card opened & discarded ?

Code

import java.io.*;

class OutSequenceException extends Exception
{
 public String toString()
 {
  return "OutSequenceException: Invalid Number Entered !\nProgram Terminating....";
 }
}

class Card
{
 public static void main(String[] args)
 {
  try
  {

   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
   //Array to store inputs and sorted sequence
   int[] a = new int[60];
   int[] b = new int[60];

   boolean flag=false;
 
   int count=0, index=0, skips, n;

   System.out.print("Enter Limit (13,26,39,52) :");
   n = Integer.parseInt(br.readLine());

   if(n!=13 && n!=26 && n!=39 && n!=52)
    throw new OutSequenceException();
    

   System.out.println("Provide Inputs");
   
   for(int i=0; i<n; i++)
   {
    a[i]=Integer.parseInt(br.readLine());

    if(a[i]>n)
     throw new OutSequenceException();

   }

   System.out.print("Enter number of skips: ");
   skips = Integer.parseInt(br.readLine());
   

   for(int i=0; i<n; i++)
   {
    //if flag is true means skips are done and b[i]=0 so no element placed there
    if(flag  && b[i]==0)
    {
     b[i]=a[count];
     count++;//next card to be placed
     flag=false;
    }


    /* 
       if previous if not executed because flag=false but some element 
       is there then also this will not execute hence skip will not 
       be incremented rather i will increase and next position 
       will be checked 
    */

    if(b[i]==0) //means previous if is not executed and no element is placed there
    {
     index++; 
     if(index==skips)
     {
      flag=true;
      index=0;
     }
     else
      flag=false;
    }

    //Reset the loop
    if(i==(n-1))
     i=-1;

    //Exit
    if(count==n)
     break;    
    
   }   
 
   //Finally print the result
   for(int i=0; i<n; i++)
    System.out.println(b[i]);

  }
  catch(Exception e)
  {
   System.out.println(e);
  }  
 }
}

2's Complement using C Programming

Definition

Property

Two's complement representation allows the use of binary arithmetic operations on signed integers, yielding the correct 2's complement results.

Positive Numbers

Positive 2's complement numbers are represented as the simple binary.

Negative Numbers

Negative 2's complement numbers are represented as the binary number that when added to a positive number of the same magnitude equals zero.

Integer		2's Complement
Signed	Unsigned
5	5	0000 0101
4	4	0000 0100
3	3	0000 0011
2	2	0000 0010
1	1	0000 0001
0	0	0000 0000
-1	255	1111 1111
-2	254	1111 1110
-3	253	1111 1101
-4	252	1111 1100
-5	251	1111 1011

Note:  The most significant (leftmost) bit indicates the sign of the integer; therefore it is sometimes called the sign bit.

If the sign bit is zero,

then the number is greater than or equal to zero, or positive.

If the sign bit is one,

then the number is less than zero, or negative.

Calculation of 2's Complement

To calculate the 2's complement of an integer, invert the binary equivalent of the number by changing all of the ones to zeroes and all of the zeroes to ones (also called 1's complement), and then add one.

For example,

0001 0001(binary 17)      1110 1111(two's complement -17)
NOT(0001 0001)	=	1110 1110  (Invert bits)
1110 1110 + 0000 0001	=	1110 1111  (Add 1)

2's Complement Addition

Two's complement addition follows the same rules as binary addition.

For example,

5 + (-3)  =  2		0000 0101	=	+5
		+ 1111 1101	=	-3
		0000 0010	=	+2

Finally a C program to perform addition using 2's Complement.

#include<stdio.h>
#include<conio.h>
#include<math.h>
void showbits(int,int);

void main()
{
 int a,b,c,bit,d,e,f,g,i;
 char ch;
 do
 {
  clrscr();

  //accepting inputs
  printf("\nEnter the number of bits: ");
  scanf("%d",&bit);
  printf("Enter two numbers to be added:- \n");
  scanf("%d",&a);
  scanf("%d",&b);
  c=a+b;

  //Ones Complement
  d=~(a);
  e=~(b);

  if(a<0)
   f=a;
  else
   f=d+1;

  if(b<0)
   g=b;
  else
   g=e+1;

  //addition
  printf("\nAddition: \n");
  printf("\t ");
  showbits(f,bit);
  printf("\n");
  printf("\t+");
  showbits(g,bit);
  printf("\n\t");

  for(i=0;i<=bit;i++)
   printf("-");

  printf("\t ");
  showbits(c,bit);
  printf("\n");
  printf("\t= %d",c);

  if(c>=(-1*(pow(2,bit-1)))&&(c<=(pow(2,bit-1)-1)))
   printf("\n\nResult Status: No Overflow \n");
  else
   printf("\n\nResult Status: Overflow \n");

  printf("\n\n\nDo you wish to continue? (y/n)");

  ch=getch();
 }while(ch=='y');
}

void showbits(int n,int bit)
{
 int i,k,andmask;

 for(i=(bit-1);i>=0;i--)
 {
  andmask=1<<i;
  k=n & andmask;

  k==0?printf("0"):printf("1");
 }
}

Binary Search Tree in C Data Structure

In computer science, a binary search tree (BST) is a node based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

From the above properties it naturally follows that: Each node (item in the tree) has a distinct key.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their their associated records.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays.

A binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13 

#include<stdio.h>
#include<conio.h>
#define null 0

struct t
{
 int data;
 struct t *left;
 struct t *right;
};

typedef struct t tree;
tree *ptr, *root, *q;

void inorder(tree *ptr); //left - root - right
void preorder(tree *ptr); //root - left - right
void postorder(tree *ptr); //left - right - root

void main()
{
 int val;
 char c='n';
 root = (tree *)malloc(sizeof(tree));

 clrscr();

 printf("Enter data: ");
 scanf("%d",&root->data);
 root->left=null;
 root->right=null;
 ptr=root; //set the current pointer to root

 fflush(stdin);
 printf("\nDo you want to add more nodes? (y/n)");
 c=getche();

 while(c!='n')
 {
  printf("\nEnter data: ");
  scanf("%d",&val);
  ptr=root;   //Every time start from root and traverse
  while(1)
  {
   if(val<ptr->data)
   {
    if(ptr->left==null)
    {
     q=(tree *) malloc(sizeof(tree));
     ptr->left=q;
     ptr=ptr->left;
     ptr->data=val;
     ptr->left=null;
     ptr->right=null;
     break;
    }
    else
     ptr=ptr->left;
   }
   else
   {
    if(ptr->right==null)
    {
     q=(tree *) malloc(sizeof(tree));
     ptr->right=q;
     ptr=ptr->right;
     ptr->data=val;
     ptr->left=null;
     ptr->right=null;
     break;
    }
    else
     ptr=ptr->right;
   }
  }

  printf("\nDo you want to add more nodes? (y/n)");
  c=getche();
 }

 printf("\n\n\n\n\nInorder:\n");
 inorder(root);

 printf("\n\nPreorder:\n");
 preorder(root);

 printf("\n\nPostorder:\n");
 postorder(root);

 getch();
}

void inorder(tree *ptr)
{
 //left - root - right
 if(ptr!=null)
 {
  inorder(ptr->left);
  printf("%d\t",ptr->data);
  inorder(ptr->right);
 }
}

void preorder(tree *ptr)
{
 //root - left - right
 if(ptr!=null)
 {
  printf("%d\t",ptr->data);
  inorder(ptr->left);
  inorder(ptr->right);
 }
}

void postorder(tree *ptr)
{
 //left - right - root
 if(ptr!=null)
 {
  inorder(ptr->left);
  inorder(ptr->right);
  printf("%d\t",ptr->data);
 }
}

Linked List in C Programming

#include<stdio.h>
#include<conio.h>
#define null 0

//structure of a node
struct n
{
 int data;        //data to store
 struct n *next;  //pointer to next node
};

typedef struct n node;
node *first, *p, *last;

void create(node*, int);
void display(node*, int);
void sort(node*);
int search(node*, int, int);
void Delete(node *,int);

void main()
{
 int count,d;

 clrscr();

 printf("Enter number of nodes: ");
 scanf("%d",&count);

 //creating nodes
 if(count>0)
 {
  first = (node *)malloc(sizeof(node));
  printf("Enter Data : ");
  scanf("%d",&first->data);
  first->next=null;

  count--;

  create(first,count);
 }

 printf("Displaying node contents -- \n\n\n");
 display(first,1);

 //sort operation on linked list
 sort(first);
 printf("\n\n\nAfter Sorting: \n\n");
 display(first,1);

 //search position of specified data
 printf("\n\n\nEnter data to search : ");
 scanf("%d",&d);

 count = search(first,d,1);

 if(count!=-1)
 {
     printf("Data found at %d.",count);
 }
 else
  printf("Data not found");

 //Add more nodes
 printf("\n\n\nEnter more number of nodes to add: ");
 scanf("%d",&count);

 create(last,count);
 sort(first);

 printf("\n\n\nFinal node values:");
 display(first,1);

 //Deleting a node
 printf("\n\nEnter data to delete: ");
 scanf("%d",&d);

 Delete(first,d);

 printf("\n\nAfter deletion nodes:\n ");
 display(first,1);

 getch();
}

void create(node *p,int count)
{
 if(count>0)
 {
  p->next =  (node *)malloc(sizeof(node));
  last=p=p->next;

  printf("Enter Data: ");
  scanf("%d",&p->data);
  p->next = null;

  count--;
  create(p,count);
 }
 else
  return;
}

void display(node *p, int count)
{
     if(p!=null)
     {
 printf("\nNode %d: %d",count,p->data);
 count++;
 display(p->next,count);
     }
     else
 return;
}

int search(node *p,int data, int count)
{
 if(p!=null)
 {
  if(data==p->data)
   return count;
  else
  {
   count++;
   search(p->next,data,count);
  }
 }
 else
  return -1;  //no matching node found
}

void Delete(node *p,int data)
{
 int count = search(first,data,1);

 if(count<0)
  printf("Data not found.");
 else
 {       p=first;
  count--;

  if(count==0)
   first=first->next;
  else
  {
   while(count>1)
   {
      p=p->next;
      count--;
   }

   p->next=p->next->next;
  }
 }
}

void sort(node *p)
{
 while(p!=null)
 {
  node *q = p->next;

  while(q!=null)
  {
   if(q->data<p->data)
   {
    int temp;
    temp=p->data;
    p->data=q->data;
    q->data=temp;
   }

   q=q->next;
  }
  p=p->next;
 }
}

Data Flow Diagrams (DFD) and Difference between Logical and Physical DFD

• A data flow diagram represents a software system as a labeled, directed graph.
• Data flow diagram illustrates the flow of data among a set of components.
• The components may be tasks, software components, or even abstractions of the functionality that will be included in the software system.

The data flow diagram (DFD) serves two purposes:

1. Provides an indication of how data are transformed as they move through the system.
2. Depicts the functions (and sub functions) that transform the data flow.

Symbols Used In DFD

Types of data flow diagrams (DFDs)

Data flow diagrams (DFDs) are categorized as either logical or physical. A logical DFD focuses on the business and how the business operates. It describes the business events that take place and the data required and produced by each event. On the other hand, a physical DFD shows how the system will be implemented.

Design Feature	Logical	Physical
What the model depicts	How the business operates	How hue system will be implemented (or how the current system operates)
What the process represent	Business activities	Programs, program modules and manual procedures
What the data stores represent	Collection of data, regardless of how the data is stored	Physical files and databases, manual files
Type of data source	Show data stores representing permanent data collections	Master files, transaction files. Any processes that operate at two different times must be connected by a data source
System controls	Show business controls	Show controls for validating input data, for obtaining a record (record found status), for ensuring successful completion of a process and for system security (example: Journal records)

A context diagram depicts the entire process being modeled as a single task, or box, in a process diagram. The diagram shows important interactions between the system and external agents.

A subsystem DFD contains one process per major subsystem. The DFD shows important interfaces with external agents. Each process is further represented by another DFD—an event-partitioned DFD (or diagram zero) for that subsystem.

An event-partitioned system model contains one process per event. The model shows important interfaces with external agents. If no subsystem DFD is created, the event-partitioned system model is also called diagram 0.

A DFD fragment is a portion of an event-partitioned system model that shows the process, external agents, data stores, and data flows needed to respond to a single event.

A process decomposition is a DFD that shows the internal implementation details of a single process on another DFD.

What are the advantages of DFDs?

• DFDs depict flow and boundary.
• DFD represents a graphical display of the process and is therefore a usable document that can be shown to both users and programmers. It serves the users as process verification.It serves the programmers as the schematic (blueprint) of the system from a technical perspective.
• It can be used in JAD sessions and as part of the business specification documentation.
• Most important, it can be used for maintaining and enhancing a process.

Difference between Insertion and Selection Sort

Insertion Sort	Selection Sort
Insertion sort, sorts a set of records by inserting record into an existing sorted file. The closer the file is sorted the more efficient the insertion sort becomes.	A selection sort is one in which successive elements are selected in order and placed into their proper sorted positions.
In insertion sort we know the element and search for its place.	In selection sort we know the place and search the element to be placed.
It is a live sorting technique. It can sort the data as it arrives.	It requires all the data to be present at the beginning of the sort.
This is a stable sorting algorithm.	This is not a stable sorting algorithm.
If the initial data is sorted then -
Comparisons = n*(n-1)/2 Moves = 0	Comparisons = n*(n-1)/2 Moves = 0
If the initial data is in reverse order then -
Comparisons =(n-1) Moves = 2+3+4+ ----- +n	Comparisons = n*(n-1)/2 Moves = n/2 * 3 (each swap consist of 3 moves)

Multi Key Organization [Data Structures]

This technique is used to sort a file based on multiple key values. Multi key file organization allows access to a data file by several different key fields. Example: Library file that requires access by author and by subject matter and title.

Scenario 1 can be like, sort the file based on roll number (this is key; you can also create clustered index). On an attribute may be other than roll number e.g. Class (MCA-I, MCA-II, MCA-III, …., MCA-VI) invert the file. 

Now if I wish to access the records of students from MCA-VI, I will locate the first record and will go sequentially in the linked list. This technique works great if -

• Attribute on which I am inverting is primary key or having nearly unique values
• The need is to access everybody in a particular class

Longer the list, it is going to be a clumsy scan. The list can be flexible in size.

• Selection/Search – go in a particular order;
• Insertion – will be easy in append mode;
• Deletion – 1) Re-arrange pointer     2) Mark deleted & re-arrange pointer at later point of time.

Scenario 2, records are sorted based on Roll numbers; now requirement is to get names of students starting with ‘J’. Therefore create inverted index on names where names starting with each alphabet will be stored as linked list. Now go through the linked list of ‘J’ to get all the records.

Indexed Sequential Organization [Data Structures]

This is a filing method used on direct access storage devices in which records are arranged in logical sequence by a key. Indexes to these keys permit direct access to individual records. In this file organization, the records of the file are stored one after another in the order they are added to the file. Indexed files can have random or sequential access modes. There is a range of keys (k1 to kn) that belong to a block. From key -> Block no. -> (sector no, Track no). The records need not to be sorted.

Clustered Index

If records are to be accessed sequentially and are placed at far places (different blocks) then the number of disk accesses increases resulting in inefficiency. Hence logically next records of a database should be placed on the same block to the extent possible i.e. “Records logically next should be physically close”. This storing of records in organizational way results in

1. Reduced number of disk accesses
2. On the page (block) we don’t need logical organization among records. They need not to be sorted.

Indexed File Organization [Data Structures]

A table is built on the top of the file. The queries and frequency of queries will decide the need for making index on one or more fields. There will be an space overhead for storing the table but this need must be justified. 

When the size of index table is too big, only a small portion of this table can be fetched into main memory and keeping the keys in sorted order becomes impossible. Hence this entire thing is maintained using B Tree. The same information of index table with essential organization can be represented using B Tree.

Relative File Organization [Data Structures]

There should be some logic for placing a particular record at particular place. Using hashing the address generated can’t be physical address. You can’t pinup the record at particular place. Hence hashing does not generate absolute address due to following reasons.

1. The absolute address has to be some track number, sector number
2. If we succeed and pinup a record at a particular place then we won’t be able to defragment the file at any later point of time.

h(key) -> rid : rid is the relative position of the record in the file. If 5 records can fit on a block then all the 5 records fitting on a particular block will have same rid. Hence h(key) -> bid. This block number is given to the OS routine, which maps bid to (track no, sector no). The OS routine will not perform any calculation instead it will search the mapping in a table. This is because, if you do calculation (i.e. you do pinning) then the block can’t be moved but table provide flexibility of changing the place if required by just updating the corresponding bid -> (track no, sector no) mapping in the table. This whole scheme is called Direct Access Mode. Relative file organization of DS fits well with this mode. Once file grows you have to shift entire file, therefore there will be a lot of hassle.

Insertion

• Block is partially empty – use the space
• Block is not empty – use another (overflow) block

Deletion of records will be with a marker (X). Records will be physically present but marked deleted.

File Organization Basics [Data Structures]

In data structure, file is a collection of records one after another and having fixed length.

• Insertion – At the end;
• Deletion – Anywhere;
• Search – Record by record;

In Data Structure it is called as heap, in OS it is called as sequential file. OS visualizes file as a series of blocks as it is not concerned about the contents of the file. A block is generally of the size of sector defined on disk. Disk can be hard sector (predefined sectors generally 8) or soft sector (user defined sectors which we use). OS does everything (deleting or appending records) in terms of blocks.

If we consider a disk with 8 sectors then every track will have sectors numbered from 1 to 8. Contents of the file (block) is defines using track number - sector number combination. FAT maintains this entry indicating the i^th block (b_i) is stored at track n and sector j.

Space to a file cannot be allocated in advance as it may grow beyond expectations. Hence every time when a block is required OS looks for empty block (a mark is associated with the block indicating its availability). When an available block is encountered then it is given to the file, an entry is made in the FAT and the block’s entry is deleted from available list; and finally file contents are appended.

If the FAT is too long then locating a block with desired data will be an exhaustive search. Hence in UNIX, the first 10 entries of DAT are direct addresses (directly pointing to data blocks). The 11th block will store the address of the block holding addresses of other data blocks. The 12th block will point to a block, which is pointing to other blocks holding addresses of data blocks.

Direct	Single Indirect	Double Indirect	Triple Indirect
10	500	500 X 500 = 5002	500 X 500 X 500 = 5003

Note: The number 500 will differ from OS to OS, installation to installation, machine to machine. It is size of block/size of each address.

This system supports small size files and at the same time it can support large files too. It provides quick access to small files and at the same time supports big files with little reduced efficiency. The table with 10+3 entries has to be memory resident. The direct addressing blocks can be configured if average file size is smaller or larger than predefined 10 direct blocks. A 4th level of indirection can also be added using 14th block. Levels of indirection are added in incremental manner.

Hence the advantages of UNIX FAT over traditional FAT are

1. FAT need to be memory resident and huge FAT can’t be accommodated.
2. Searching through big size FAT – As it won’t fit on memory so you need to perform multiple disk accesses and at the end you may not be having the address you were looking for. We can’t spend too much time on just locating the address of a block.

Disk Access & Block Organization

As head passes through blocks, contents are read, loaded into disk buffer and then transferred to RAM. Once the disk buffer is full, it needs some time to get flushed before other data can be placed in it.

Physical Organization	Logical Organization
In this organization, blocks are stored one after another. The R/W head moves with a constant speed. After reading b1, the disk buffer is full and the R/W head is in b2 which is the next block to be read. As we need some time to empty the disk buffer hence this organizations is not efficient.	In this organization, blocks are placed at a distance of two blocks. After reading b1, the disk buffer is full. The R/W head has to skip two blocks and during this time the disk buffer can be flushed. Hence this is an efficient block organization.

Track no. is the thing that expects physical movement of head which occurs in a jumpy manner. The track no. access requests need to be optimized with the intention of minimizing head movement on disk. Hence different disk scheduling techniques are used. As the disk scheduling algorithms optimize the head movement therefore a request placed fists may be fulfilled later.

Record Number -> Block Number -> (Track Number, Sector Number) -> Disk

If records are of fixed size then a fixed n records can be placed on a block. Never ever split record across blocks. Now translate record no. to block no. using simple calculation. E.g. if 2 records are on each block then 9th record will be on 4th block.

• B Tree: Key Value -> Record id (rid) -> Block id (bid) -> (Track number, Sector Number)
• Hashing: h (Key Value) - > Record id (rid) -> Block id (bid) -> (Track number, Sector Number)

Logical & Physical Address Space – The record with key value 50 is logical view of record. rid to bid is logical address translation. Obtaining (Track Number, Sector Number) from bid is physical address translation.

In Hashing with bucketing the rid itself will be bid. Bucket Address = Block no. Hence h(key) -> bid -> ts.