Extensible Hashing Trace

Step 1: insert 1111

Global depth g = 1

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	0	1	empty
B2	1	1	1111

Step 2: insert 1110

Global depth g = 1

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	0	1	empty
B2	1	1	1111, 1110

Step 3: insert 1101

Global depth g = 1

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	0	1	empty
B2	1	1	1111, 1110, 1101

Step 4: insert 1100

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001, 010, 011	1	empty
B2	100, 101	2	empty
B3	110	3	1101, 1100
B4	111	3	1111, 1110

Step 5: insert 1011

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001, 010, 011	1	empty
B2	100, 101	2	1011
B3	110	3	1101, 1100
B4	111	3	1111, 1110

Step 6: insert 1010

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001, 010, 011	1	empty
B2	100, 101	2	1011, 1010
B3	110	3	1101, 1100
B4	111	3	1111, 1110

Step 7: insert 1001

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001, 010, 011	1	empty
B2	100, 101	2	1011, 1010, 1001
B3	110	3	1101, 1100
B4	111	3	1111, 1110

Step 8: insert 1000

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001, 010, 011	1	empty
B2	100	3	1001, 1000
B3	101	3	1011, 1010
B4	110	3	1101, 1100
B5	111	3	1111, 1110

Step 9: insert 0111

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001, 010, 011	1	0111
B2	100	3	1001, 1000
B3	101	3	1011, 1010
B4	110	3	1101, 1100
B5	111	3	1111, 1110

Step 10: insert 0110

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001, 010, 011	1	0111, 0110
B2	100	3	1001, 1000
B3	101	3	1011, 1010
B4	110	3	1101, 1100
B5	111	3	1111, 1110

Step 11: insert 0101

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001, 010, 011	1	0111, 0110, 0101
B2	100	3	1001, 1000
B3	101	3	1011, 1010
B4	110	3	1101, 1100
B5	111	3	1111, 1110

Step 12: insert 0100

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001	2	empty
B2	010	3	0101, 0100
B3	011	3	0111, 0110
B4	100	3	1001, 1000
B5	101	3	1011, 1010
B6	110	3	1101, 1100
B7	111	3	1111, 1110

Step 13: insert 0011

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001	2	0011
B2	010	3	0101, 0100
B3	011	3	0111, 0110
B4	100	3	1001, 1000
B5	101	3	1011, 1010
B6	110	3	1101, 1100
B7	111	3	1111, 1110

Step 14: insert 0010

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001	2	0011, 0010
B2	010	3	0101, 0100
B3	011	3	0111, 0110
B4	100	3	1001, 1000
B5	101	3	1011, 1010
B6	110	3	1101, 1100
B7	111	3	1111, 1110

Step 15: insert 0001

Global depth g = 3

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000, 001	2	0011, 0010, 0001
B2	010	3	0101, 0100
B3	011	3	0111, 0110
B4	100	3	1001, 1000
B5	101	3	1011, 1010
B6	110	3	1101, 1100
B7	111	3	1111, 1110

Step 16: insert 0000

Global depth g = 3 (final structure)

#	Directory entries (prefixes)	Local depth	Keys in bucket
B1	000	3	0001, 0000
B2	001	3	0011, 0010
B3	010	3	0101, 0100
B4	011	3	0111, 0110
B5	100	3	1001, 1000
B6	101	3	1011, 1010
B7	110	3	1101, 1100
B8	111	3	1111, 1110

Extensible Hashing Insertion Trace (bucket capacity = 3)

Step 1: insert 1111

Step 2: insert 1110

Step 3: insert 1101

Step 4: insert 1100

Step 5: insert 1011

Step 6: insert 1010

Step 7: insert 1001

Step 8: insert 1000

Step 9: insert 0111

Step 10: insert 0110

Step 11: insert 0101

Step 12: insert 0100

Step 13: insert 0011

Step 14: insert 0010

Step 15: insert 0001

Step 16: insert 0000