How do I draw Extendible Hashing/Skip List diagrams using Tikz Library?

For hash indexes there is a rather neat implementation at https://github.com/doersino/hashing-indexes-tikz Here's the extendible index provided in the example.tex:

\documentclass[12pt, a4paper]{article}
\usepackage{exthashidx}
\begin{document}
  \begin{center}
    \scalebox{0.8}{
      \begin{tikzpicture}
        % directory
        \xyshift{+00mm}{+00mm}{\exthashidxdirectoryeight{directory}{3}}
        % buckets
        \xyshift{+20mm}{+50mm}{\exthashidxbucketfour{A}{3}{}{}{64}{16}}
        \xyshift{+20mm}{+25mm}{\exthashidxbucketfour{B}{2}{1}{5}{21}{}}
        \xyshift{+20mm}{+00mm}{\exthashidxbucketfour{C}{2}{10}{}{}{}}
        \xyshift{+20mm}{-25mm}{\exthashidxbucketfour{D}{2}{15}{7}{51}{}}
        \xyshift{+20mm}{-50mm}{\exthashidxbucketfour{A2}{3}{4}{12}{20}{36}}
        % links
        \exthashidxlink{directory-000}{A}
        \exthashidxlink{directory-001}{B}
        \exthashidxlink{directory-010}{C}
        \exthashidxlink{directory-011}{D}
        \exthashidxlink{directory-100}{A2}
        \exthashidxlink{directory-101}{B}
        \exthashidxlink{directory-110}{C}
        \exthashidxlink{directory-111}{D}
      \end{tikzpicture}
    }
  \end{center}
\end{document}

For the first graph I used only TikZ. There are some tricks. Multiple parts in a node are not so easy to use : I use inner xsep=2ex because I don't find another way. I use macros from pgfmath to write directly number in the base 2. Remark : I get a problem to have the same height with a node part of f and with the height of g node ?? (if someone has an idea about this ?)

Final version

\documentclass{article}
\usepackage{tikz}  
\usetikzlibrary{shapes,calc,arrows}
\begin{document}

\begin{tikzpicture}[every text node part/.style={align=center},>=latex']
%%%%%%%%%%%%%%%%%  The nodes %%%%%%%%%%%%% 
% multiple parts rectangle split
  \node[name=f,rectangle split, rectangle split parts=16, draw,rectangle split empty part height=2ex,rectangle split empty part depth=2ex,inner xsep=2ex]
{ };

% numbers in base 2 node at the right  
\foreach \n [count=\num from 0] in  {one,two,three,four,five,six,seven,eight,nine,ten,eleven,twelve,thirteen,fourteen,fifteen,sixteen}{%
\pgfmathsetbasenumberlength{4}
\pgfmathdectoBase{\mynumber}{\num}{2}
\node[anchor=east] at (f.\n\space west) {\mynumber};} % trick \space is necessary

% node at the left side problem to find the height
% problem to put a node inside correctly
\node[draw,minimum width=12 ex,minimum height=5ex]  (g-one) at ($(f.one\space east)+(2,0)$) {$32\ \hphantom{00}$}  ; % trick \hphantom{00} to have the same position                                                      
\node[draw,anchor=north west,inner sep =1pt,font=\small] at (g-one.north west){3}; 

\node[draw,minimum width=12 ex,minimum height=5ex]  (g-two) at ($(f.two\space split east)+(2,0)$) {$18\ \hphantom{00}$}  ;    
\node[draw,anchor=north west,inner sep =1pt,font=\small] at (g-two.north west){3};

\node[draw,minimum width=12 ex,minimum height=5ex]  (g-four) at ($(f.four\space east)+(2,0)$) {$23\ \hphantom{0}9$}  ;
\node[draw,anchor=north west,inner sep =1pt,font=\small] at (g-four.north west){1}; 

% little trick with ($(f.five\space split east)+(2,0)$)
\node[draw,minimum width=12 ex,minimum height=5ex]  (g-five) at ($(f.five\space split east)+(2,0)$) {$4\hphantom{0}\ 20$}  ;    
\node[draw,anchor=north west,inner sep =1pt,font=\small] at (g-five.north west){4}; 

\node[draw,minimum width=12 ex,minimum height=5ex]  (g-six) at ($(f.seven\space east)+(2,0)$) {$10\ \hphantom{00}$}  ;
\node[draw,anchor=north west,inner sep =1pt,font=\small] at (g-six.north west){3}; 

\node[draw,minimum width=12 ex,minimum height=5ex]  (g-thirteen) at ($(f.thirteen\space east)+(2,0)$) {$44\ 76$}  ;
\node[draw,anchor=north west,inner sep =1pt,font=\small] at (g-thirteen.north west){4}; 

%%%%%%%%%%%%%%%%%% Th edges %%%%%%%%%%%%%%%%%%%%%%%
 %  Simple edges
\draw[->] (f.one) -- (g-one);  
\draw[->] (f.two) -- ($(g-four.west)+(0,2pt)$);   
\draw[->] (f.three) -- (g-two);
\draw[->] (f.four) -- (g-four.west);
\draw[->] (f.five) -- (g-five.west); 
\draw[->] (f.seven) -- (g-six.west);   
\draw[->] (f.thirteen) -- (g-thirteen); 
% More complex
\draw[->,rounded corners=.5 cm] (f.sixteen) to +(1,0) to ($(f.four)+(1,-3pt)$) to  ($(g-four.west)+(0,-3pt)$); 
% little trick to avoid the mix of arrows with ($(f.four)+(1,-3pt)$)
\draw[->,rounded corners=.5 cm] (f.nine) to +(.75,0) to ($(f.one)+(.75,-3pt)$) to  ($(g-one.west)+(0,-3pt)$); 

\draw[rounded corners=.5 cm] (f.six) to +(1,0) to ($(f.five)+(1,0)$); 
\draw[rounded corners=.5 cm] (f.eight) to +(1,0) to ($(f.seven)+(1,0)$);
\draw[rounded corners=.5 cm] (f.ten) to +(1,0) to ($(f.nine)+(1,0)$); 
\draw[rounded corners=.5 cm] (f.twelve) to +(1,0) to ($(f.eleven)+(1,0)$); 
\draw[rounded corners=.5 cm] (f.fourteen) to +(1,0) to ($(f.thirteen)+(1,0)$); 

\draw[->] (f.eleven) to ++(3,0) to [out=0,in=0] (g-two); 
\draw[->] (f.fifteen) to ++(3,0) to [out=0,in=0] (g-six);
\end{tikzpicture}

The second graph is relatively easy to draw with tkz-graph. First we define the names of vertices x;y from 0;0 x=row and y= column

\documentclass{article}
\usepackage{tkz-graph} % from ctan or TL2011 one file tkz-graph.sty 

\begin{document}
  \begin{tikzpicture}
  \SetGraphUnit{1.5}
  \SetVertexNormal[Shape    = rectangle,MinSize=.8 cm]
   %%%%%%%%%%%%%%%%% vertices %%%%%%%%%%%%%%%%%%% 
   %  name of node x;y  x row y column

\Vertex[L=$-\infty$] {0;0}

\foreach \num [count=\n from 0] in  {1,2,3}
 {\NO[L=$-\infty$](0;\n){0;\num}}        
% No = north (initial node) {new node}  L=label 
\foreach \num/\label [count=\n from 0] in  
    {1/11,2/15,3/17,4/28,5/31,6/55,7/56,8/61,9/+\infty}
      {\EA[L=$\label$](\n;0){\num;0}} 
\foreach \num [count=\n from 0] in  {1,2,3}{%
     \NO[L=$+\infty$](9;\n){9;\num}}  

\foreach \num [count=\n from 0] in  {1,2,3} {%
    \NO[L=$31$](5;\n){5;\num}}   

\foreach \no/\label  in  {1/11,2/15,6/55,7/56} {%
    \NO[L=$\label$](\no;0){\no;1} } 

%%%%%%%%%%%%%%%%% edges %%%%%%%%%%%%%%%%%%%%%%%
 \foreach \num [count=\n from 1] in  {0,...,8}  {\Edge(\num;0)(\n;0)}

 \foreach \num [count=\n from 1] in  {0,...,2}  
 {\Edge(0;\num)(0;\n)  \Edge(5;\num)(5;\n)  \Edge(9;\num)(9;\n)}

\foreach \num  in  {1,2,6,7} {\Edge(\num;0)(\num;1)}   

\foreach \num [remember=\num as \lastnum (initially 0)] in  {5,9}  
 {\Edge(\lastnum;3)(\num;3) }  

\foreach \num [remember=\num as \lastnum (initially 0)] in  {5,9}  
 {\Edge(\lastnum;2)(\num;2)} 

\foreach \num [remember=\num as \lastnum (initially 0)] in  {1,2,5,6,7,9}  
 {\Edge(\lastnum;1)(\num;1)}     
   \end{tikzpicture}   
\end{document}